시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB178382923.016%

문제

우주제국의 황제 명우는 최근 서로 전쟁을 하던 $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$개의 워프 게이트를 설치하는 비용의 최솟값이 출력되어야 한다.

예제 입력 1

4 4
1 2 1
2 3 2
3 4 3
1 4 4

예제 출력 1

7
6
6
8
W3sicHJvYmxlbV9pZCI6IjE5Mjk3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiTG9naXN0aWNhbCBNZXRyb3BvbGlzIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2YjBcdWM4ZmNcdWM4MWNcdWFkNmRcdWM3NTggXHVkNjY5XHVjODFjIFx1YmE4NVx1YzZiMFx1YjI5NCBcdWNkNWNcdWFkZmMgXHVjMTFjXHViODVjIFx1YzgwNFx1YzdjMVx1Yzc0NCBcdWQ1NThcdWIzNTggJE4kXHVhYzFjIFx1ZDU4OVx1YzEzMVx1Yzc0NCBcdWM1YjRcdWJkODBcdWM5YzBcdWI5YWNcdWI4NWMgXHVjODEwXHViODM5XHVkNTg4XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNzc0ICROJFx1YWMxY1x1Yzc1OCBcdWQ1ODlcdWMxMzFcdWM1ZDBcdWIyOTQgXHVkM2M5XHVkNjU0XHVhYzAwIFx1Y2MzZVx1YzU0NFx1YzY1NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHVhZTMwXHVjNWQwIFx1YjM1NFx1ZDU3NFx1YzExYyBcdWJhODVcdWM2YjBcdWIyOTQgJE4kXHVhYzFjIFx1ZDU4OVx1YzEzMSBcdWFjMDRcdWM1ZDAgXHVjMTFjXHViODVjIFx1Yzc3NFx1YjNkOVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIzYzRcdWI4NWQgJE4tMSRcdWMzMGRcdWM3NTggXHVjNmNjXHVkNTA0IFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWIwOThcdWM3NTggXHVjNmNjXHVkNTA0IFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWJhNzQgXHViNDUwIFx1ZDU4OVx1YzEzMSBcdWFjMDRcdWM3NTgmbmJzcDtcdWM3NzRcdWIzZDlcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTU4XHViYTcwLCBcdWM1YjRcdWI1YTQgXHVkNTg5XHVjMTMxXHViNGU0XHVjNzQ0IFx1YzViNFx1YjVhNCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjkwXHViMGQwXHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWJlNDRcdWM2YTlcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJhODVcdWM2YjBcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Y2QxZCAkTSRcdWFjMDBcdWM5YzAgXHVjMzBkXHVjNzU4IFx1YzZjY1x1ZDUwNCBcdWFjOGNcdWM3NzRcdWQyYjhcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmE4NVx1YzZiMFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHVkNTg5XHVjMTMxIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjIDxzdHJvbmc+XHVjOGZjXHVjNjk0IFx1ZDU4OVx1YzEzMTxcL3N0cm9uZz5cdWM3M2NcdWI4NWMgXHVjMGJjXHVjNTQ0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM2YjBcdWM4ZmMgXHVjODFjXHVhZDZkXHVhY2ZjJm5ic3A7XHVjNWYwXHVhY2IwXHViNDE4XHViMjk0IFx1YzZjY1x1ZDUwNCBcdWFjOGNcdWM3NzRcdWQyYjhcdWI5N2MgXHViOWNjXHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViYTg1XHVjNmIwXHViMjk0IFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWM4ZmNcdWM2OTQgXHVkNTg5XHVjMTMxXHVhY2ZjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YjI5NCBcdWM2Y2NcdWQ1MDQgXHVhYzhjXHVjNzc0XHVkMmI4XHViOTdjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWI1MzBcdWM5YzBcdWM5YzAgXHVjNTRhXHVhY2UwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHViOWNjXHViNGU0XHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDU4OVx1YzEzMVx1Yzc0NCBcdWM4ZmNcdWM2OTQgXHVkNTg5XHVjMTMxXHVjNzNjXHViODVjIFx1YzBiY1x1Yzc0NCBcdWI1NGMgJE4tMSRcdWFjMWNcdWM3NTggXHVjNmNjXHVkNTA0IFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJE4kLCAkTSQoJDEgJmxlOyBOICZsZTsgMTAwXFwsMDAwJCwgJE4tMSAmbGU7IE0gJmxlOyAzMDBcXCwwMDAkKVx1Yzc3NCBcdWFjZjVcdWJjMzEgXHVkNTU4XHViMDk4XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTSRcdWFjMWMgXHVjOTA0XHVjNzU4IFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzc0XHVjMTI0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM2Y2NcdWQ1MDQgXHVhYzhjXHVjNzc0XHVkMmI4XHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCAkeCQsICR5JCwgJGMkKCQxICZsZTsgeCAmbHQ7IHkgJmxlOyBOJCwgJDEgJmxlOyBjICZsZTsgMTBeOSQpXHVhYzAwIFx1YWNmNVx1YmMzMSBcdWQ1NThcdWIwOThcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0ICR4JFx1YmM4OCBcdWQ1ODlcdWMxMzFcdWFjZmMgJHkkXHViYzg4IFx1ZDU4OVx1YzEzMVx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVjNmNjXHVkNTA0IFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWFjNzRcdWMxMjRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmU0NFx1YzZhOVx1Yzc3NCAkYyQmbmJzcDtcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViNDUwIFx1ZDU4OVx1YzEzMVx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViMjk0IFx1YzVlY1x1YjdlYyBcdWJjODggXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzZjY1x1ZDUwNCBcdWFjOGNcdWM3NzRcdWQyYjhcdWI5N2MgXHVhYzc0XHVjMTI0XHVkNTU4XHViYTc0LCBcdWJhYThcdWI0ZTAgXHViNDUwIFx1ZDU4OVx1YzEzMVx1YWMwNCBcdWM3NzRcdWIzZDlcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWM4M1x1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JE4kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODgmbmJzcDtcdWQ1ODlcdWMxMzFcdWM3NDQgXHVjOGZjXHVjNjk0IFx1ZDU4OVx1YzEzMVx1YzczY1x1Yjg1YyBcdWMwYmNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVkNTg5XHVjMTMxXHVhYzA0IFx1Yzc3NFx1YjNkOVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIzYzRcdWI4NWQgJE4tMSRcdWFjMWNcdWM3NTggXHVjNmNjXHVkNTA0IFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWIyOTQmbmJzcDtcdWJlNDRcdWM2YTlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzc0IFx1Y2Q5Y1x1YjgyNVx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTkyOTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNU1Qgd2l0aCBNZXRyb3BvbGlzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGlzIHByb2JsZW0sIHdlIHdpbGwgY29uc2lkZXIgd2VpZ2h0ZWQgdW5kaXJlY3RlZCBncmFwaHMgd2hlcmUgYWxsIGVkZ2VzIGhhdmUgcG9zaXRpdmUgd2VpZ2h0cy48XC9wPlxyXG5cclxuPHA+V2UgYXJlIGdpdmVuIGEgd2VpZ2h0ZWQgdW5kaXJlY3RlZCBncmFwaCAkRyQgd2hpY2ggY29uc2lzdHMgb2YgJG4kIHZlcnRpY2VzIG51bWJlcmVkIGZyb20gJDEkIHRvICRuJC4gQW1vbmcgdGhlIHNwYW5uaW5nIHRyZWVzIG9mICRHJCwgdGhlIE1TVCAoTWluaW11bSBTcGFubmluZyBUcmVlKSB3aXRoIDxzdHJvbmc+bWV0cm9wb2xpcyB2ZXJ0ZXg8XC9zdHJvbmc+ICRpJCBpcyB0aGUgb25lIHRoYXQgY29udGFpbnMgZXZlcnkgcG9zc2libGUgZWRnZSB3aXRoIHRoZSBtZXRyb3BvbGlzICh0aGUgdmVydGV4ICRpJCkgYW5kIG1pbmltaXplcyB0aGUgc3VtIG9mIGVkZ2Ugd2VpZ2h0cyBpbiBpdC4gTGV0IHRoaXMgZWRnZSB3ZWlnaHQgc3VtIGJlICRTX2kkLiBZb3VyIHRhc2sgaXMgdG8gY2FsY3VsYXRlICRTX2kkIGZvciBldmVyeSB2ZXJ0ZXggJGkkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICRuJCBhbmQgJG0kOiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGFuZCBlZGdlIGluIHRoZSBncmFwaCwgcmVzcGVjdGl2ZWx5ICgkMSBcXGxlcSBuIFxcbGVxIDEwXjUkLCAkbiAtIDEgXFxsZXEgbSBcXGxlcSAzIFxcdGltZXMgMTBeNSQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJG0kIGxpbmVzIGRlc2NyaWJlcyBhIHNpbmdsZSBlZGdlIGFuZCBjb250YWlucyB0aHJlZSBpbnRlZ2VycywgJHgkLCAkeSQsIGFuZCAkYyQgd2hpY2ggbWVhbiB0aGF0IHRoZXJlIGlzIGFuIGVkZ2UgYmV0d2VlbiB2ZXJ0aWNlcyAkeCQgYW5kICR5JCBvZiB3ZWlnaHQgJGMkICgkMSBcXGxlcSB4ICZsdDsgeSBcXGxlcSBuJCwgJDEgXFxsZXEgYyBcXGxlcSAxMF45JCkuPFwvcD5cclxuXHJcbjxwPkl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgZ2l2ZW4gZ3JhcGggaXMgY29ubmVjdGVkLCBhbmQgdGhlcmUgaXMgYXQgbW9zdCBvbmUgZWRnZSBiZXR3ZWVuIGV2ZXJ5IHBvc3NpYmxlIHBhaXIgb2YgdmVydGljZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgJG4kIGxpbmVzLiBUaGUgJGkkLXRoIGxpbmUgbXVzdCBjb250YWluIGFuIGludGVnZXIgJFNfaSQ6IHRoZSB3ZWlnaHQgb2YgdGhlIE1TVCB3aXRoIG1ldHJvcG9saXMgdmVydGV4ICRpJC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d