ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1811. Dual-SIM Phone

Time limit: 2.0 second
Memory limit: 64 MB
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 ≤ 104; 0 ≤ k ≤ 105). n is equal to the total number of mobile operators. Each of the following k lines contains integers x, y and c (1 ≤ x, yn; 1 ≤ c ≤ 109), 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.


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
1 1 3
2 1 4
No solution
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.