Task
Time limit:
1000 ms,
Memory limit:
32 Mb
Требуется найти в связном графе остовное дерево минимального веса в котором есть данное ребро.
Формат файла входных данных:
Первая строка входного файла содержит два натуральных числа 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
Вывод:
7