З метою підготовки до проведення олімпіади з інформатики мер вирішив забезпечити надійним електропостачанням усі школи міста. Для цього необхідно провести лінію електропередач від альтернативного джерела електроенергії “Майбуття” до однієї зі шкіл міста (до якої не має значення), а також з'єднати лініями електропередач деякі школи між собою.

Вважається, що школа має надійне електропостачання, якщо вона безпосередньо пов'язана з джерелом “Майбуття”, або з однією з шкіл, які мають надійне електропостачання.

Відома вартість з'єднання між деякими парами шкіл. Мер міста вирішив обрати одну з двох найбільш економічних схем електропостачання (вартість схеми дорівнює сумі вартості пар шкіл).

Напишіть програму, яка обчислює вартість двох найбільш економних схем альтернативного електропостачання шкіл.

Формат вхідних даних

У першому рядку знаходяться два натуральні числа, розділені пробілом: \(N\) (\(3 ≤ N ≤ 100\)), кількість шкіл у місті, і \(M\) – кількість можливих з'єднань між ними.

У кожному з наступних рядків \(M\) знаходяться по три числа: \(A_i, B_i, C_i\), розділених пробілами, де \(C_i\) – вартість прокладки лінії електропостачання (\(1 ≤ C_i ≤ 300\)) від школи \(A_i\) до школи \(B_i\) (\(i=1,2,…,N \)).

Формат вихідних даних

У єдиному рядку повинні міститися два натуральні числа \(S_1\) і \(S_2\), розділених пробілом – дві найменші вартості схем (\(S_1 ≤ S_2\)). \(S_1=S_2\) тоді і тільки тоді, коли є кілька схем надійного електропостачання найменшої вартості.

Гарантується, що для вхідних даних є дві різні схеми надійного електропостачання.

Приклад вхідних даних

5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

Приклад вихідних даних

110 121