ACM соревнование и нарушение связи
Для подготовки к "Первому национальному школьному ACM соревнованию" (в 20??) мэр города решил обеспечить все школы надежным источником энергии. (Мэр очень боится нарушения связи). Для этого электростанция "Будущее" и одна из школ (не имеет значение какая) должны быть соединены; а также некоторые другие школы также должны быть присоединены к сети.
Школа имеет достаточно электроэнергии, если либо она присоединена напрямую к электростанции "Будущее", либо к другой школе, имеющую достаточно электроэнергии. Вам известна стоимость соединения некоторых школ друг с другом. Мэр желает найти два самых дешевых плана соединения школ. Стоимость плана равна сумме стоимостей всех входящих в него соединений между школами. Помогите мэру найти эти два самых дешевых плана.
Входные данные
Первая строка содержит два числа, разделенных одним пробелом: количество школ в городе n (3 ≤ n ≤ 100) и количество m имеющихся связей между ними. Каждая из следующих m строк содержит три числа a[i], b[i], c[i], где c[i] - стоимость связи (1 ≤ c[i] ≤ 300) между школами a[i] и b[i]. Школы пронумерованы целыми числами от 1 до n.
Выходные данные
В одной строке вывести два числа, разделенных одним пробелом: стоимости двух самых дешевых планов соединений. Пусть S[1] - самый дешевый план, а S[2] второй по дешевизне план. Тогда S[1] = S[2] только если это два самых дешевых плана, иначе S[1] ≤ S[2]. Считайте, что всегда можно найти S[1] и S[2].