Минимальный каркас

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

Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником “Майбуття”, либо с одной из тех школ, которые имеют надежное электроснабжение.

Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).

 

Напишите программу, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.

 

В первой строке входного файла находятся два натуральных числа, разделенных пробелом: N (3 <= N <= 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1 <= C_i <= 300) от школы Ai до школы Bi (i=1,2,…,N).

 

В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом – две наименьшие стоимости схем (S₁ <= S₂). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.

 

Гарантируется, что для входных данных существует две различные схемы надёжного электроснабжения.
 

Примеры

№	Входные данные	Выходные данные
1	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

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

Президент хочет отремонтировать некоторое множество дорог так, чтобы суммарная стоимость ремонта была минимальной и из любого города Берляндии можно было бы добраться до любого другого, пользуясь только отремонтированными дорогами.

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

Гарантируется, что всегда найдется необходимое множество дорог.

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

В первой строке задано два целых числа - n и m (2 <= n <= 300000, n - 1  <= m <= 300000).

В следующих m строках содержатся три числа - u, v и w (1 <= u, v <= n, 0 <= w <= 10⁹) - дорога между городами u и v, стоимость ремонта которой w.

Ввод	Вывод
3 3 1 2 1 1 2 3 1 3 4	5
2 4 1 2 0 1 2 1 1 2 2 1 2 3	0

(с) Ибрахим Ахмад, 2018