eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Знайомство

Знайомство

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

Делегація школярів N-ської області прибула на Всеросійську олімпіаду. Насправді, точніш буде сказати "школярок", адже вона складається з n талановиих дівчат. Зрозуміло, організатори не були готові до такого стану справ і поселення виявилось несподіваним: кожну школярку поселили у окремий одномістний номер готелю.

На наступний день у той же готель поселили ще декілька делегацій, у одну з яких входить школяр Слава. Він не міг пройти повз таку незвичну делегацію і вирішив пізднім вечором перед туром познайомитись хоча б з однією дівчиною з делегації N-ської області. Слава знає, що у цей час ті готуються до туру, читаючи книги, і не налаштовані приймати гостей. Тому він вирішив діяти наступним чином. Перш за все він виключить електричний запобіжник біля однієї з кімнат, в результаті чого там погасне світло. Залишившись у темноті, дівчина трішки злякається, а потім відправиться до однієї зі своїх подруг (до тієї, до якої йти ближче усього), щоб продовжувати підготовку до туру. І саме на цьому шляху вона буде найбільш беззахисна...

Слава хоче взнати, наскільки багато часу у нього може бути виділено на знайомство, а також яку дівчиу слід вибрати для цього.

Вхідні дані

У першому рядку входу записані цілі числа n та k (1n, k10^5) - кількість дівчат у делегації, а також кількість пар дівчат, які є подругами. У наступних k рядках записано по три числа a[i], b[i] та w[i] - номери дівчат, які є подругами, а також відстань між їхніми кімнатами (1a[i], b[i]n, a[i]b[i], 1w[i]10^5). Гарантується, що ніяка пара подруг не зустрінеться двічі. Гарантується, що у кожної дівчини є подруга.

Вихідні дані

У першому рядку виведіть одне ціле число - максимальний час на знайомство, який він може собі забезпечити. У другому рядку виведіть номер школярки, яку слід вибрати. Якщо існує декілька школярок, які забезпечують максимальний час знайомства, виведіть довільну з них.

Приклад

Вхідні дані #1
3 3
1 2 1
2 3 3
3 1 2
Вихідні дані #1
2
3
Джерело 15 Международная олимпиада для школьников ЛКШ для параллелей B,A',A