Farmer John wants to connect his water distribution system cheaply, but he doesn't want his rival, Farmer Snidely, to be able to predict the actual routes he chooses. FJ knows that this kind of problem usually asks for the cheapest way to connect water pipes, so he decides to avoid that and use the second cheapest way instead.

Given a list of all the bidirectional pipes that might connect a set of ~W~ ~(3 \leq W \leq 2000)~ water stations (any one of which can be made into a well) along with the costs for no more than ~P (P \leq 20,000)~ pipes, find the second cheapest way to distribute water. No pipe connects a station to itself; no two pipes connect the same pair of stations.

It is guaranteed that there is only one cheapest way to distribute the water and that there are at least two ways to distribute the water. All costs are positive integers that fit into a signed 16-bit entity. A water station is identified by its ID number, which is an integer in the range ~1...W~.

INPUT FORMAT

Line 1: Two space-separated integers, ~W~ and ~P~.

Lines 2..P+1: Each line describes a single pipe and contains three space-separated integers: a water station that is one endpoint of a pipe, a water station that is the other endpoint of a pipe, and the cost of that pipe.

SAMPLE INPUT

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

OUTPUT FORMAT

A single line with a single integer that is the second lowest cost to construct a water distribution system.

SAMPLE OUTPUT

20