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

Tavrida NU Akai contest. Petrozavodsk training camp. Summer 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. 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.

Input

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

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

inputoutput
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.
To submit the solution for this problem go to the Problem set: 1811. Dual-SIM Phone