Студент Петя хочет заработать на рассылке SMS-спама. Естественно, он хочет тратить на отправку SMS как можно меньше денег, при этом отправлять SMS как можно быстрее. Петя решил купить себе новый Dual-SIM телефон, в который можно вставить SIM-карты сразу двух операторов. С помощью такого телефона он сможет отправлять SMS на нужный номер через того оператора, через которого эта услуга будет дешевле.

К сожалению, не все операторы сотовой связи предоставляют возможность отправлять SMS на номера всех остальных операторов. Помогите Пете выбрать SIM-карты двух операторов так, чтобы он смог отправлять SMS на номера всех операторов, а максимальная стоимость отправки одного сообщения была бы как можно меньше.

В первой строке записаны целые числа n и k (2 ≤ n ≤ 10⁴; 0 ≤ k ≤ 10⁵). Число n равняется общему количеству операторов сотовой связи. В каждой из следующих k строк записаны целые числа x, y и c (1 ≤ x, y ≤ n; 1 ≤ c ≤ 10⁹), которые означают, что с номера оператора x на номер оператора y можно отправить SMS за стоимость c.

Выведите максимальную стоимость отправки одного SMS при оптимальном выборе пары операторов, или «No solution», если выбрать пару операторов требуемым образом невозможно.