Educational Codeforces Round 3 |
---|
Закончено |
Дан связный неориентированный взвешенный граф без петель и кратных ребер, состоящий из n вершин и m ребер.
Для каждого ребра графа (u, v) найдите вес такого остовного дерева, что это ребро (u, v) входит в него, и при этом вес этого остовного дерева минимален.
Весом остовного дерева называется сумма весов ребер, входящих в остовное дерево.
В первой строке записаны два целых числа n и m (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — количество вершин и ребер в графе.
В каждой из следующих m строк записаны три целых числа ui, vi, wi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) — вершины графа, соединенные i-м ребром, и вес этого ребра.
Выведите m строк: i-я строка должна содержать минимальный вес такого остовного дерева, содержащего i-ое ребро.
Ребра нумеруются от 1 до m в порядке их появления во входных данных.
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
Название |
---|