P6061 [Cheer Up Wuhan] Epidemic Investigation

City W has suffered a serious pneumonia outbreak. To deal with the epidemic, City W needs to conduct a巡回 (xunhui, patrol-style) investigation of every community under its administration. City W has a total of $n$ blocks. The blocks are connected by $m$ distinct directed roads. No road goes from a block to itself, and the graph is guaranteed to be weakly connected. Traveling along each road costs a certain amount of fuel. Now you need to send some staff members to visit every block. For each staff member, you assign them some blocks. Then the staff member will repeatedly cycle through these blocks in the given order, completing one cycle per week. Note that a staff member will only inspect the blocks assigned to them; for blocks they pass through between assigned blocks, they will not get off the vehicle. Also, to avoid wasting manpower, each block can be inspected by at most one staff member. Of course, if necessary, they may pass through the same block multiple times. The cost for a staff member is defined as follows: if a staff member is assigned only one block $u$, then each week they need to pay a staying cost of $a_u$. If they are assigned more than one block, then their weekly cost is the sum of fuel costs along the roads for going around these points once and finally returning to the starting point. You need to determine, assuming an unlimited number of staff members, the minimum total weekly cost required to fully patrol City W.

The first line contains two integers $n,m$, with the meanings as described above. The second line contains $n$ integers, the array $a$. The next $m$ lines each contain three integers $u_i,v_i,w_i$, indicating that there is a **directed edge** from $u_i$ to $v_i$, and the travel cost is $w_i$.

Output one integer, representing the answer.

Constraints: for all data, $1\leq n\leq 500,1\leq m\leq \min\{5000,n\times(n-1)\},0\leq a_i,w_i\leq 10^9$. The graph is guaranteed to be weakly connected, with no self-loops and no multiple edges. For different test groups, the constraints are as follows: | Test Group ID | $n\leq$ | $m\leq$ | Special Property | | :-: | :-: | :-: | :-: | | $1\sim 6$ | $15$ | $100$ | $\times$ | | $7\sim 10$ | $500$ | $5000$ | For all edges, $w_i=0$. | | $11\sim 14$ | $500$ | $500$ | $n=m$ and every node has out-degree $1$. | | $15\sim 20$ | $500$ | $5000$ | $\times$ | Translated by ChatGPT 5