Petr, a student, wants to make money with SMSspam. Of course he wants to spend as little money as possible for sending a message and send messages as quick as he can. Petr decided to buy a new DualSIM mobile phone, which can work with SIMcards of two different mobile operators simultaneously. Now Petr can send a message to a certain phone number via one of two chosen operators which requests less money for that.
Unfortunately, not all mobile operators allow sending messages to numbers of all other operators via them. Help Petr choose a pair of operators in such a way that he would be able to send messages to numbers of all operators and the maximum cost of sending a message would be minimal possible.
Input
The first line contains integers n and k
(2 ≤ n ≤ 10^{4}; 0 ≤ k ≤ 10^{5}).
n is equal to the total number of mobile operators.
Each of the following k lines contains integers x, y
and c (1 ≤ x, y ≤ n; 1 ≤ c ≤ 10^{9}), which means
that Petr can send an SMS via operator x to a phone number of operator y for cost c.
Output
Output the maximal cost of sending an SMS, which can be achieved by choosing an optimal pair of operators, or “No solution” if it is impossible to choose a required pair of operators.
Samples
input  output 

4 13
1 1 1
1 2 3
1 3 3
1 4 5
2 1 2
2 2 1
2 3 2
3 1 4
3 3 4
3 4 1
4 1 2
4 2 3
4 4 3
 2

2 2
1 1 3
2 1 4
 No solution

Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.