Petr, a student, wants to make money with SMS-spam. 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 Dual-SIM mobile phone, which can work with SIM-cards 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.

The first line contains integers n and k (2 ≤ n ≤ 10⁴; 0 ≤ k ≤ 10⁵). 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⁹), which means that Petr can send an SMS via operator x to a phone number of operator y for cost c.

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.