ACM змагання і порушення зв'язку#1107
Напередодні "Першого Національного Шкільного ACM Конкурсу" мер міста вирішив забезпечити всі школи надійним джерелом енергії (мер дуже турбується про відключення електроенергії). Для цього електростанцію "Майбутнє" та одну зі шкіл (не має значення, яку саме) необхідно з'єднати; додатково, деякі інші школи також мають бути під'єднані до мережі.
Школа вважається такою, що має надійне джерело енергії, якщо вона з'єднана безпосередньо з електростанцією "Майбутнє" або з іншою школою, яка вже має надійне джерело енергії. Відомо вартість підключення деяких пар шкіл. Мер бажає знайти два найдешевші плани підключення. Вартість плану — сума вартостей усіх з'єднань, включених до нього. Допоможіть меру знайти ці два найдешевші плани підключення.
У першому рядку містяться два цілих числа, розділені пробілом: (3 \le n \le 100) — кількість шкіл у місті, та — кількість можливих з'єднань між ними. Кожен із наступних рядків містить три цілі числа a_i, b_i, c_i, де c_i (1 \le c_i \le 300) — вартість підключення шкіл a_i та b_i. Школи пронумеровані від до .
Виведіть два цілих числа, розділених пробілом — вартості двох найдешевших планів підключення. Нехай S_1 — найменша вартість, а S_2 — наступна найменша. Якщо S_1 = S_2, то існують два різних найдешевших плани; інакше, S_1 \le S_2. Можна вважати, що завжди можливо знайти такі S_1 та S_2.
Приклад 1
Приклад 2