Description

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

Format

Input

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

Output

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

Samples

413
111
123
133
145
212
221
232
314
334
341
412
423
443

2

Limitation

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