ACM соревнование и нарушение связи
ACM соревнование и нарушение связи
Для подготовки к "Первому национальному школьному 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
.
4 4 1 2 2 1 4 5 1 3 4 2 3 3
10 11
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