Description

Farmer John needs to transport his milk to various sales points. During transportation, the milk can first be sent to some sales points and then distributed from there to other sales points. The smaller the total transportation distance, the lower the cost. Farmer John aims for low-cost transportation, but he doesn't want his competitors to know his specific transportation plan, so he prefers to use the second smallest cost transportation plan instead of the smallest. Now, please help find this transportation plan.

Input Format

The first line contains two integers, $N$ and $M$, representing the number of vertices and edges, respectively.

Each of the next $M$ lines contains three integers, $x$, $y$, and $z$, indicating the two endpoints $x$, $y$ of a road and the distance $z$ between them.

Output Format

Output only one line, the second smallest transportation plan.

Sample 1

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450

Data Range and Hints

For all data, $1\le N\le 500$, $1\le M\le 10^4$, $1\le z\le 10^9$. The data may contain duplicate edges.