Система непересекающихся множеств

Требуется найти в связном графе остовное дерево минимально веса.

 

Первая строка входного файла содержит два натуральных числа n и m - количество вершин и ребер графа соответственно (1≤n≤20000, 0≤m≤100000). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi - номера концов ребра и его вес соответственно (1≤bi,ei≤n, 0≤wi≤100000).

 

Граф является связным.

 

Выведите единственное целое число - вес минимального остовного дерева.
 

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

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

 

Однако, этот момент может наступить до того, как будут построены все мосты. Вам необходимо определить такое минимальное количество мостов, после строительства которых (в порядке, определенном планом), можно будет попасть с любого острова на любой другой.

 

Первая строка содержит два числа: число островов N (1≤N≤10000) и количество мостов в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера городов, которые соединяет очередной мост в плане.

 

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

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

 

Требуется найти в связном графе остовное дерево минимального веса в котором есть данное ребро.

 

Формат файла входных данных:

 

Первая строка входного файла содержит два натуральных числа N, M - количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei, Wi номера концов ребра и его вес соответственно (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). В последней строке вводится данное ребро B, E, W.

 

Формат файла выходных данных:

 

Единственная строка выходного файла должна содержать одно натуральное число - вес минимального остовного дерева c данным ребром. 

 

Ввод:

 

4 4

1 2 1

2 3 2

3 4 5

4 1 4

1 4 7

 

Вывод:

10