Знакомство
Делегация школьников N-ской области прибыла на Всероссийскую олимпиаду. На самом деле, точнее будет сказать "школьниц", ведь она состоит из n талантливых девушек. Разумеется, организаторы не были готовы к такому положению вещей и расселение оказалось неожиданным: каждую школьницу поселили в отдельный одноместный номер гостиницы.
На следующий день в ту же гостиницу заселили ещё несколько делегаций, в одну из которых входит школьник Слава. Он не мог пройти мимо такой необычной делегации и решил поздним вечером перед туром познакомиться хотя бы с одной девушкой из делегации N-ской области. Слава знает, что в это время те готовятся к туру, читая книги, и не расположены принимать гостей. Поэтому он решил действовать следующим образом. Первым делом он выключит электрический предохранитель около одной из комнат, в результате чего там погаснет свет. Оставшись в темноте, девушка немного испугается, а затем отправится к одной из своих подруг (к той, до которой идти ближе всего), чтобы продолжать готовиться к туру. И именно по пути она будет наиболее беззащитна...
Слава хочет узнать, насколько много времени у него может оказаться на знакомство, а также какую девушку следует выбрать для этого.
Входные данные
В первой строке записаны целые числа n и k (1 ≤ n, k ≤ 10^5) - количество девушек в делегации, а также количество пар девушек, являющихся подругами. В следующих k строках записано по три числа a[i], b[i] и w[i] - номера девушек, являющихся подругами, а также расстояние между их комнатами (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i], 1 ≤ w[i] ≤ 10^5). Гарантируется, что никакая пара подруг не встретится дважды. Гарантируется, что у каждой девушки есть подруга.
Выходные данные
В первой строке выведите одно целое число - максимальное время на знакомство, которое он может себе обеспечить. Во второй строке выведите номер школьницы, которую следует выбрать. Если существует несколько школьниц, которые обеспечивают максимальное время знакомства, выведите любую из них.