Logistical Metropolis

우주제국의 황제 명우는 최근 서로 전쟁을 하던 $N$개 행성을 어부지리로 점령했다. 이제 이 $N$개 행성에는 평화가 찾아왔다.

명우는 여기에 더해 $N$개 행성이 서로 이동할 수 있도록 $N-1$쌍의 워프 게이트를 설치하려고 한다. 워프 게이트 하나를 설치하면 두 행성 사이의 이동이 가능해지며, 어떤 행성들을 어떤 방식으로 연결하느냐에 따라 비용이 달라질 수 있다. 명우는 현재 총 $M$가지 쌍의 워프 게이트를 연결할 수 있다.

명우는 $N$개 행성 중 하나를 주요 행성으로 골라, 자신의 우주제국과 연결되는 워프 게이트를 만들 것이다. 명우는 선택된 주요 행성과 연결되는 워프 게이트를 비용을 따지지 않고 최대한 많이 만들고 싶다. 각각의 행성을 주요 행성으로 삼았을 때, $N-1$개의 워프 게이트를 설치하는 비용의 최솟값을 구하는 프로그램을 작성하라.

첫 번째 줄에 두 정수 $N$, $M$($1 \le N \le 100\,000$, $N-1 \le M \le 300\,000$)이 공백 하나로 구분되어 주어진다.

다음 $M$개 줄의 각 줄에는 건설 가능한 워프 게이트의 정보를 나타내는 세 정수 $x$, $y$, $c$($1 \le x < y \le N$, $1 \le c \le 10^9$)가 공백 하나로 구분되어 주어진다. 이는 $x$번 행성과 $y$번 행성을 잇는 워프 게이트를 건설하는 데 비용 $c$가 필요하다는 뜻이다. 같은 두 행성에 대한 정보는 여러 번 주어지지 않는다. 모든 워프 게이트를 건설하면 모든 두 행성 간 이동이 가능한 것이 보장된다.

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