15481번 - 그래프와 MST

문제

총 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 ≤ 10⁹)

출력

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

제한

힌트