Problem D
Friend Finding

Dilawar, Haavard and Kjerand are best friends, and they are moving to the same neighborhood. The neighborhood consists of $N$ intersections, and $M$ roads connecting them. It takes the same amount of time to walk a road in both directions. The friends want to choose the position of their new homes according to a very strict criteria. They want to live in a way that minimizes the time it takes for all three to meet at an intersection. Their new homes must be placed on top of an intersection, and they will live at three distinct intersections. It is guaranteed that a solution exists.

Input

The first line contains $N$ and $M$, the number of intersections, and roads respectively. Then follows $M$ lines with the values $u_ i$, $v_ i$, and $t_ i$, which describe the starting position of the i’th road, the intersection at which it ends, and the time it takes to travel from one end to the other. Roads start and end at different intersections, and the edges will only appear once in the input.

Output

Output the number $T$, which states how long time it has to take for them to meet at an intersection, given that they place their new homes optimally.

Limits

• $3 \leq N, M \leq 100\, 000$

• $1 \leq t_ i \leq 10\, 000$

• $0 \leq u,v \leq N-1$

• The neighborhood is connected.

4 4
0 1 2
0 2 3
0 3 4
2 3 3

3