시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB209069542936.050%

문제

총 N개의 정점과 M개의 간선으로 이루어져 있는 무방향 가중치 연결 그래프 G가 있다. 그래프 G는 루프가 없고, 두 정점을 연결하는 간선은 최대 1개이다.

각각의 간선 (u, v)에 대해서, 그 간선을 포함하는 최소 스패닝 트리의 가중치 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000)

둘째 줄부터 M개의 줄에 간선의 정보 u, v, w가 주어진다. u와 v를 연결하는 간선의 가중치가 w라는 뜻이다. (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 109

출력

각각의 간선마다 그 간선을 포함하는 최소 스패닝 트리의 가중치 합을 출력한다. 간선은 입력받은 순서대로 출력한다.

예제 입력 1

5 8
1 2 5
2 3 4
1 3 2
3 4 8
4 5 3
3 5 6
1 4 9
2 5 1

예제 출력 1

11
10
10
14
10
12
15
10

예제 입력 2

6 8
1 2 2
2 3 8
3 4 1
4 1 9
4 5 7
5 6 2
6 4 6
3 6 9

예제 출력 2

19
19
19
20
20
19
19
22

출처