Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Roads in the Kingdom

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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 *u*_{i} and *v*_{i} and its length is *l*_{i}. 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

The first line contains the integer *n* (3 ≤ *n* ≤ 2·10^{5}) — 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^{9}) — 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.

Examples

Input

3

1 2 4

2 3 5

1 3 1

Output

5

Input

5

2 3 7

3 1 9

4 1 8

3 5 4

4 5 5

Output

18

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2018 08:47:24 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|