Для подготовки к "Первому национальному школьному ACM соревнованию" (в 20??) мэр города решил обеспечить все школы надежным источником энергии. (Мэр очень боится нарушения связи). Для этого электростанция "Будущее" и одна из школ (не имеет значение какая) должны быть соединены; а также некоторые другие школы также должны быть присоединены к сети.

Школа имеет достаточно электроэнергии, если либо она присоединена напрямую к электростанции "Будущее", либо к другой школе, имеющую достаточно электроэнергии. Вам известна стоимость соединения некоторых школ друг с другом. Мэр желает найти два самых дешевых плана соединения школ. Стоимость плана равна сумме стоимостей всех входящих в него соединений между школами. Помогите мэру найти эти два самых дешевых плана.

Входные данные

Первая строка содержит два числа, разделенных одним пробелом: количество школ в городе n (3 ≤ n ≤ 100) и количество m имеющихся связей между ними. Каждая из следующих m строк содержит три числа ai, bi, ci, где ci - стоимость связи (1 ≤ ci ≤ 300) между школами ai и bi. Школы пронумерованы целыми числами от 1 до n.

Выходные данные

В одной строке вывести два числа, разделенных одним пробелом: стоимости двух самых дешевых планов соединений. Пусть S1 - самый дешевый план, а S2 второй по дешевизне план. Тогда S1 = S2 только если это два самых дешевых плана, иначе S1 ≤ S2. Считайте, что всегда можно найти S1 и S2.