Roads in the Kingdom

Description:

Input:

The first line contains the integer n (3 ≤ n ≤ 2·10⁵) — the number of towns and roads.

The next n lines contain the roads description. The i-th from these lines contains three integers u_i, v_i, l_i (1 ≤ u_i, v_i ≤ n, 1 ≤ l_i ≤ 10⁹) — 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:

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

Sample Input:

3
1 2 4
2 3 5
1 3 1

Sample Output:

5

Sample Input:

5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5

Sample Output:

18