Ural1811 Dual Sim Phone

时间限制:10s      空间限制:128MB

题目描述

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


输入格式

一行包含格隔的两个整数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^40<=k<=10^5   1<=x;y<=n   1<=c<=10^9


题目来源

没有写明来源