Optimal Daily Route for Visiting All Cows

Farmer John owns N ranches (numbered from \(1\) to \(N\), with \(5 \le N \le 10,000\)), each housing one cow. The ranches are connected by \(P\) bidirectional paths (\(N-1 \le P \le 100,000\)). The \(j\)-th path connects ranch \(S_j\) and ranch \(E_j\) (\(1 \le S_j, E_j \le N, \; S_j \neq E_j\)) and takes \(L_j\) units of time to traverse (\(0 \le L_j \le 1000\)). There is at most one direct path between any two ranches.

The cows are upset about the reduction in the transportation network. To cheer them up, you must visit every cow at least once per day. Each time you arrive at a ranch \(i\) (even if only passing through), you must spend \(C_i\) units of time talking with the cow (\(1 \le C_i \le 1000\)).

You will spend every night at the same ranch (your lodging choice is free). Moreover, just before sleeping and right after waking up you must speak with the cow at your lodging ranch, resulting in two extra conversations there each day.

Your task is to choose an optimal lodging ranch and plan a daily route such that you visit every cow at least once and the total time spent (both traveling and conversing) is minimized. It can be shown that an optimal route can be constructed by first selecting a Minimum Spanning Tree (MST) of the graph and then performing a depth-first traversal (a DFS tour) on that tree. In such a tour, every MST edge is traversed twice, except that by choosing the lodging ranch wisely you can save the time corresponding to the longest distance from that ranch in the MST.

Formally, let \(T\) be the MST with total edge weight \(L_T\) and let \(S = \sum_{i=1}^{N} C_i\). For a lodging ranch \(b\), if \(d(b)\) is the maximum distance from \(b\) to any other node in \(T\), then an optimal tour based on \(T\) takes time

[ \text{Total Time} = 2L_T + S + C_b - d(b). ]

Your task is to compute the minimum total time over all choices of lodging ranch \(b\).

inputFormat

The input begins with a line containing two integers \(N\) and \(P\) separated by a space.

The next line contains \(N\) integers: \(C_1, C_2, \ldots, C_N\), where \(C_i\) is the conversation time at ranch \(i\).

Each of the following \(P\) lines contains three integers \(S_j\), \(E_j\), and \(L_j\), indicating that there is a bidirectional path between ranch \(S_j\) and ranch \(E_j\) with travel time \(L_j\).

outputFormat

Output a single integer, the minimum total time required to visit every cow at least once per day under the optimal choice of lodging ranch.

sample

5 4
3 2 4 6 5
1 2 1
2 3 2
3 4 3
4 5 4

33