409211: GYM103462 C Circle Minimal

As we all know, a tree has $$$n$$$ nodes and $$$n - 1$$$ edges.

We define the length of the circle as the sum of the weights of all edges on the circle.

Now we have a graph with $$$n$$$ nodes and $$$n$$$ edges, you can move at most one edge on the graph to minimize the length of the circle on the graph.

If you choose to move an edge, there can be no self-loops(which means $$$u \rightarrow u$$$) and duplicated edges after the movement, and the graph is connected (at least one path can reach any two points on the graph).

Little H need you output the length of the minimal circle.

The first line contains a single integer $$$n(3 \leq n \leq 10^5)$$$.

Each of the next $$$n$$$ lines contains three integers $$$u_i, v_i, w_i(1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9)$$$, representing the $$$i$$$-th edge connect $$$u_i$$$ and $$$v_i$$$ which weights is $$$w_i$$$.

Print a single integer, denoting the answer.

5
1 2 1
1 5 1
3 4 1
1 4 10
2 3 10

3

5
1 2 1
2 3 1
3 4 1
1 4 10
1 5 10

3