ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1811. Dual-SIM телефон

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

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
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
Источник задачи: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.