Бікфордів шнур#2635
У прекрасний сонячний день Їжачок прогулювався своєю улюбленою галявиною. Раптом він побачив щось незвичне, чого раніше тут не було. Здалеку це виглядало як клубок переплутаних мотузок. Підійшовши ближче, розплутавши його і розглянувши матеріал, Їжачок зрозумів, що це детонуючий шнур.
Уважно оглянувши знахідку, стало зрозуміло, що той, хто це зробив, мав дуже багато вільного часу, адже шнур був заплутаний і зав'язаний величезною кількістю вузлів! Після ретельного підрахунку з'ясувалося, що є вузлів і з'єднань між ними. Кожне з'єднання з'єднує два вузли і згорає рівномірно. Коли вузол підпалюється, усі з'єднання, які до нього приєднані, запалюються.
Проте Їжачкові ця знахідка не сподобалася, і він вирішив її знищити. Для цього він використав сірник, що випадково опинився у нього в кишені. Він може запалити будь-який вузол, після чого вся конструкція почне згоряти. А оскільки Їжачок — зайнятий смішарик, він хоче, щоб ця конструкція згоріла якомога швидше. Допоможи йому визначити, який вузол потрібно підпалити.
У першому рядку задано два цілих числа та (2 \le n \le 100, 1 \le m \le n \cdot (n - 1) / 2) — кількість вузлів і кількість шнурів між ними.
У наступних рядках описуються з'єднання між вузлами, кожен з яких містить три цілих числа a_i, b_i та t_i (1 \le a_i, b_i \le n, a_i \ne b_i, 1 \le t_i \le 1000) — номери вузлів, які з'єднані -м шнуром, та кількість секунд, за які цей шнур повністю згорить з будь-якого кінця.
Кожна пара вузлів з'єднана не більше ніж одним шнуром. Гарантується, що вся конструкція згорить повністю, якщо підпалити будь-який з її вузлів.
Виведіть два числа: номер вузла, який потрібно підпалити, і за який час вся конструкція повністю згорить.
Приклад 1