E. Минимальное остовное дерево по каждому ребру
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан связный неориентированный взвешенный граф без петель и кратных ребер, состоящий из 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