Требуется найти в связном графе остовное дерево минимального веса в котором есть данное ребро.
Формат файла входных данных:
Первая строка входного файла содержит два натуральных числа 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 |