Требуется найти в связном неориентированном графе остовное дерево минимального веса.
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество вершин и ребер графа соответственно (1 ≤ N ≤ 20 000, 0 ≤ M ≤ 100 000). Следующие M строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei и Wi – номера концов ребра и его вес соответственно (1 ≤ Bi, Ei ≤ N, 0 ≤ Wi ≤ 100 000).
В выходной файл OUTPUT.TXT выведите целое число – вес минимального остовного дерева.
№ | INPUT.TXT | OUTPUT.TXT |
1 | 4 4
1 2 1
2 3 2
3 4 5
4 1 4 | 7 |