Дан связный неориентированный взвешенный граф без петель и кратных ребер, состоящий из n вершин и m ребер.
Для каждого ребра графа (u, v) найдите вес такого остовного дерева, что это ребро (u, v) входит в него, и при этом вес этого остовного дерева минимален.
Весом остовного дерева называется сумма весов ребер, входящих в остовное дерево.
Выходные данные
Выведите m строк: i-я строка должна содержать минимальный вес такого остовного дерева, содержащего i-ое ребро.
Ребра нумеруются от 1 до m в порядке их появления во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4
|
9
8
11
8
8
8
9
|