P2916 [USACO08NOV] Cheering up the Cow G

Farmer John has $N$ pastures (numbered $1$ to $N$, $5 \leq N \leq 10,000$), each inhabited by one cow. These pastures are connected by $P$ bidirectional paths ($N-1 \leq P \leq 100,000$). Each path $j$ connects pastures $S_j$ and $E_j$ ($1 \leq S_j \leq N$; $1 \leq E_j \leq N$; $S_j \neq E_j$), and traversing it takes $L_j$ units of time ($0 \leq L_j \leq 1,000$). There is at most one direct path between any pair of pastures. John plans to remove as many roads as possible while keeping all pastures connected. He knows the cows will be very sad after the demolition, so he plans to comfort them afterward. John may choose any pasture to start his comforting tour. After he has visited all cows, he must return to his starting pasture. Each time he passes pasture $i$, he must spend $C_i$ ($1 \leq C_i \leq 1000$) units of time to talk with the cow there; even if he has already talked before, he must stop and talk again. Note that both when setting out and when returning, he must talk to the cow at the starting pasture. Assume Farmer John follows your recommendation on which paths to keep, and you also choose the optimal lodging pasture. Compute the minimal total time required while ensuring that each cow is visited at least once.

- Line $1$: Two space-separated integers: $N$ and $P$. - Lines $2$ to $N+1$: Line $i+1$ contains one integer: $C_i$. - Lines $N+2$ to $N+P+1$: Line $N+j+1$ contains three space-separated integers: $S_j$, $E_j$, and $L_j$.

- Line $1$: A single integer, the minimal total time needed to visit all cows (including the two chats at the lodging pasture).

```cpp +-(15)-+ / \ / \ 1-(5)-2-(5)-3-(6)--5 \ /(17) / (12)\ / /(12) 4------+ Keep these paths: 1-(5)-2-(5)-3 5 \ / (12)\ /(12) *4------+ ``` Choose pasture $4$ as the lodging pasture, visit in the order $4 \to 5 \to 4 \to 2 \to 3 \to 2 \to 1 \to 2 \to 4$, and finally return to sleep. The total time is $176$ units. Translated by ChatGPT 5