Minimizing Traversal Cost in a Weighted Graph

You are given an undirected graph with N vertices (numbered from 0 to N-1) and M edges. The graph has no self‐loops or multiple edges. Among these edges, exactly N-1 edges have a weight of 1 and form a spanning tree. All remaining edges have weights in the range \(\lceil\frac{N}{3}\rceil \le w \le N\) (in particular, these weights are relatively high compared to 1).

Your task is to plan a route so that you visit all vertices at least once while minimizing the total cost (sum of weights of the edges traversed). You are allowed to traverse an edge more than once (paying its cost each time) and you may start at any vertex. Note that although you may revisit vertices, you only need to visit each vertex at least once.

Hint: When restricted to the spanning tree (edges with weight 1), one common strategy is to perform a DFS traversal. The total cost of such a traversal is \(2(N-1)\), but by choosing a route that starts and ends at two vertices that are far apart in the tree (i.e. the two endpoints of the tree's diameter), one can save exactly the length of that diameter. In other words, if no extra edge is used, the minimum cost is

[ 2(N-1) - \text{diameter}(T), ]

However, an extra edge \(e\) connecting two vertices \(u\) and \(v\) (with weight \(w_e\)) may let you replace the tree path between \(u\) and \(v\) (of length \(d(u,v)\)) at an extra cost of \(w_e\). This yields an effective saving of \(d(u,v) - w_e\) if positive. Thus, the overall optimal saving is

[ \max\Bigl(\text{diameter}(T),; \max_{e;\text{extra}}{d(u,v)-w_e}\Bigr), ]

and the minimum traversal cost is

[ 2(N-1) - \max\Bigl(\text{diameter}(T),; \max_{e;\text{extra}}{d(u,v)-w_e}\Bigr). ]

</p>

Your program must implement this logic.

inputFormat

The first line contains two integers N and M. Each of the following M lines contains three integers u, v, and w, representing an undirected edge between vertices u and v with weight w.

outputFormat

Output a single integer — the minimum total weight required to visit every vertex at least once.

sample

4 3
0 1 1
1 2 1
2 3 1

3

</p>