Знайомство
Делегація школярів 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). Гарантується, що ніяка пара подруг не зустрінеться двічі. Гарантується, що у кожної дівчини є подруга.
Вихідні дані
У першому рядку виведіть одне ціле число - максимальний час на знайомство, який він може собі забезпечити. У другому рядку виведіть номер школярки, яку слід вибрати. Якщо існує декілька школярок, які забезпечують максимальний час знайомства, виведіть довільну з них.