#3346. Ural1811 Dual Sim Phone

题目描述

彼得一个学生，想要从短信业务中获利。 当然他也想花最少的钱发送信息，并且
尽快地发送信息。因此，他想买一个双卡手机，对于两个运营商的卡可以同时工作。现在，他可以发送短信给某个手话号码，通过两个运营商中花钱更少的一个。
不幸的是，并非所有手机运营商可以通过他们发送短信给其他运营商的手话号码。帮助他选反一对运营商，使他能发送短信给所有运营商的手话号码，而且发送短信的最大费用最少 。

输入格式

一行包含格隔的两个整数n和k。n是手机运营商的数目。接下来k行， 每行含有
整数x; y; c，表示可以花费c元通过运营商x发送一条短信给运营商y的手话号码。

输出格式

输出发送一条短信最大 的花费。如果不可能，输出"No solution"。

样例

样例输入

413  

111  

123  

133  

145  

212  

221  

232  

314  

334  

341  

412  

423  

443  

样例输出

2

数据范围与提示

2<=n<=10^4，0<=k<=10^5 ，1<=x;y<=n ，1<=c<=10^9