Знайомство#5273
Група талановитих школярок з N-регіону прибула на національну олімпіаду. Делегація складається з дівчат, і через непередбачену ситуацію кожна з них була поселена в окремий одномісний готельний номер.
В один із вечорів перед туром олімпіади раптове відключення електроенергії трапилося в одному з номерів. Дівчина з цього номера вирішила продовжити підготовку й вирушила до своєї найближчої подруги в інший номер. Час, який вона витратить на шлях до своєї найближчої подруги, залежить від відстані між їхніми номерами.
Організатори хочуть дізнатися, якій учасниці, у разі відключення електроенергії в її номері, доведеться долати найбільшу відстань до найближчої подруги, і якою може бути ця максимальна відстань.
У першому рядку задано два числа та (1 \leq n,\, k \leq 10^{5}) — кількість дівчат у делегації та кількість пар подруг між ними.
Кожен із наступних рядків містить три числа a_i, b_i та w_i: індекси двох подруг та відстань між їхніми номерами (1 \leq a_i,\, b_i \leq n, a_i \neq b_i, 1 \leq w_i \leq 10^{5}).
Гарантується, що жодна пара подруг не зустрічається більше одного разу, і в кожної дівчини є хоча б одна подруга.
У першому рядку виведіть максимальну відстань, яку може довестися подолати дівчині до своєї найближчої подруги у випадку відключення електроенергії в її номері.
У другому рядку виведіть номер дівчини, якій відповідатиме ця максимальна відстань. Якщо таких дівчат декілька, виведіть будь-яку з них.
Приклад 1