Roads in the Kingdom
Contest: Codeforces Round 427 (Div. 2)
Difficulty rating: 2500
Tags: dfs and similar, dp, graphs, trees

In the Kingdom K., there are n towns numbered with integers from 1 to n. The towns are connected by n bi-directional roads numbered with integers from 1 to n. The i-th road connects the towns ui and vi and its length is li. There is no more than one road between two towns. Also, there are no roads that connect the towns with itself.

Let's call the inconvenience of the roads the maximum of the shortest distances between all pairs of towns.

Because of lack of money, it was decided to close down one of the roads so that after its removal it is still possible to reach any town from any other. You have to find the minimum possible inconvenience of the roads after closing down one of the roads.

Input format:
The first line contains the integer n (3 ≤ n ≤ 2·105) — the number of towns and roads.

The next n lines contain the roads description. The i-th from these lines contains three integers ui, vi, li (1 ≤ ui, vi ≤ n, 1 ≤ li ≤ 109) — the numbers of towns connected by the i-th road and the length of the i-th road. No road connects a town to itself, no two roads connect the same towns.

It's guaranteed that it's always possible to close down one of the roads so that all the towns are still reachable from each other.

Output format:
Print a single integer — the minimum possible inconvenience of the roads after the refusal from one of the roads.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
1 2 4
2 3 5
1 3 1

Example output:
5

Example input:
5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5

Example output:
18

Editorial:
Observation I.
The given graph is a cycle with hanged trees. So, we can remove the edge only from the cycle, the resulting graph will be a tree.
Observation II.
We can minimize the distances only between the pairs of vertexes such that path between them goes through the cycle's edges. Let's say that these pairs are interesting.
Solution.
Let's find the cycle using dfs. Let its length be k. Let's number the vertices in it from 1 to k in round order. We will try to remove edges between 1 and 2, 2 and 3, ..., 1 and k and calculate the maximum distance between the interesting pairs.
We need to pre-compute the following:
• di — the maximum depth of the tree hanged to the i-th vertex of the cycle.
• wi — the length of the edge between the i-th vertex of the cycle and the next in the round order.
• pref_diami — the maximum distance between the interesting pairs such that their vertexes are in the trees hanged to the vertexes 1, 2, ..., i of the cycle.
• suff_diami — the maximum distance between the interesting pairs such that their vertexes are in the trees hanged to the vertexes i, i + 1, ..., k of the cycle.
• pref_fari — the maximum distance from the first vertex of the cycle to the vertexes that are in the trees hanged to the vertexes 1, 2, ..., i of the cycle.
• suff_fari — the maximum distance from the first vertex of the cycle to the vertexes that are in the trees hanged to the vertexes i, i + 1, ..., k of the cycle.
Also suff_diamk + 1 = suff_fark + 1 =  - ∞.
These pre-computations can be done in linear time.
If we delete the edge between the i-th vertex of the cycle and the next in the round order, then the maximum distance between the interesting pairs is max(pref_far[i] + suff_far[i + 1], pref_diam[i], suff_diam[i + 1]).
After we found the optimal edge to remove, we remove it and find the diameter of the resulting tree. It can be done with 2 dfs'es. Let vertex v be the farest from 1. Let vertex u be the farest from v. It's easy to prove that the path between u and v is the diameter.
Time complexity: O(n). Memory complexity: O(n).