문제
우주 제국의 황제 명우는 최근 서로 전쟁을 하던 N개 행성을 어부지리로 점령했다.
이제 이 N개의 행성에는 평화가 찾아왔다.
여기에 더해서 명우는 N개 행성 간에 서로 이동이 가능하도록 N−1쌍의 워프 게이트를 설치하려고 한다.
하나의 워프 게이트를 설치하면 두 행성간의 이동이 가능하며,
어떤 행성들을 어떤 방식으로 연결하느냐에 따라 비용의 차이가 있을 수 있다.
명우는 현재 총 M가지 쌍의 워프 게이트를 연결할 수 있다.
명우는 N개의 행성 중 하나를 골라 주요 행성으로 삼아 자신의 우주 제국과 연결되는 워프 게이트를 만들 것이다.
명우는 선택된 주요 행성과 연결되는 워프 게이트를 비용을 따지지 않고 최대한 많이 만들고 싶다.
각각의 행성을 주요 행성으로 삼을 때 N−1개의 워프 게이트를 설치하는 비용의 최솟값을 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 두 정수 N, M (1 ≤ N ≤ 100,000, N-1 ≤ M ≤ 300,000)이 공백 하나로 구분되어 주어진다.
다음 M개 줄의 각 줄에는 건설 가능한 워프 게이트의 정보를 나타내는 세 정수
x, y, c(1 ≤ x < y ≤ N, 1 ≤ c ≤ 109)가 공백 하나로 구분되어 주어진다.
이는 x번 행성과 y번 행성을 잇는 워프 게이트를 건설하기 위해 비용이 c만큼 필요하다는 뜻이다.
같은 두 행성에 대한 정보는 여러 번 주어지지 않는다. 모든 워프 게이트를 건설하면, 모든 두 행성간 이동이 가능한 것이 보장된다.
출력
N개의 줄에 걸쳐 정답을 출력한다. i번째 줄에는 i번 행성을 주요 행성으로 삼을 때,
모든 행성간 이동이 가능하도록 N−1개의 워프 게이트를 설치하는 비용의 최솟값이 출력되어야 한다.
예제
4 4
1 2 1
2 3 2
3 4 3
1 4 4
7
6
6
8
로그인해야 코드를 작성할 수 있어요.