Logistical Metropolis

우주제국의 황제 명우는 최근 서로 전쟁을 하던 $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 ≤ 10^9$)가 공백 하나로 구분되어 주어진다. 이는 $x$번 행성과 $y$번 행성을 잇는 워프 게이트를 건설하기 위해 비용이 $c$ 필요하다는 뜻이다. 같은 두 행성에 대한 정보는 여러 번 주어지지 않는다. 모든 워프 게이트를 건설하면, 모든 두 행성간 이동이 가능한 것이 보장된다.

$N$개의 줄에 걸쳐 정답을 출력한다. $i$번째 줄에는 $i$번 행성을 주요 행성으로 삼을 때, 모든 행성간 이동이 가능하도록 $N-1$개의 워프 게이트를 설치하는 비용의 최솟값이 출력되어야 한다.