Легенда

Арсений Иголкин любит искусство, особенно непризнанное и малоизвестное. В каждом городе он ищет какой-нибудь авангардный или отдалённый музей и часами бродит по нему, разглядывая экспонаты. В очередной поездке у Арсения было совсем немного времени, поэтому из вариантов осталась только галерея современного искусства. Тогда Арсений решил найти в галерее самые непопулярные экспонаты и сосредоточиться на них.

Представим галерею в виде графа из экспонатов и двунаправленных переходов между ними. Вес перехода – это время, за которое от одного экспоната можно добраться до другого. Между двумя экспонатами может быть более одного перехода. Представим блуждающего посетителя, который начиная от случайного экспоната делает 100 случайных перемещений по галерее. При этом вероятность выбрать переход пропорциональна весу этого перехода (чтобы было время осмыслить увиденное).

Определите экспонат, который будет посещаться реже всего. Учитываются только посещения с переходов (то есть посещение в самом начале блуждания не рассматривается).

Формат входных данных: два натуральных числа через пробел, число экспонатов N и число переходов M. Далее идёт M строк, в каждой три числа, первые два – целые номера экспонатов (нумерация с нуля) и вес перехода (вещественное ненулевое число).

Формат выходных данных: единственное целое число, наименее популярный экспонат.

Решение принимается, если выбранный экспонат является одним из трёх наименее популярных, выбранных авторским решением.

Ограничение времени   1.5 секунд
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

Для решения этой задачи у вас есть 20 попыток.

Видео-разбор