문제
바이트랜드는 최근 전력난이 심각하다. 전기를 절약하기 위한 여러 방안 중에 가로등에 대한 문제도 거론되었다. 바이트랜드에서는 시민의 안전을 위하여 밤에는 모든 가로등을 밝히고 있는데 가로등을 밝히는 데는 1미터당 1비트코인(헐!!!)이 든다고 한다.
전기 절약을 위하여 시민의 안전을 최소한으로 보장하면서 일부 가로등을 소등하고자한다. 채택된 방안은 바이트랜드의 임의의 한 교차로에서 다른 한 임의의 교차로까지 이르는 경로가 적어도 하나는 존재하도록 가로등을 켜는 것이었다.
바이트랜드에 대한 정보가 주어질 때, 시민의 안전을 최소한으로 보장하면서 전기를 절약하고자 한다. 절약할 수 있는 최대 금액은 얼마일까? 이를 구하는 프로그램을 작성하시오.
입력
첫 행에 바이트랜드의 교차로 수 M과 도로의 수 N이 입력된다. M(1 ≤ M ≤ 200,000), N( M-1 ≤ N ≤200,000) 다음 행부터 N행에 걸쳐 도로에 대한 정보 s, e, d가 공백으로 구분하여 주어진다. s와 e는 교차로 번호이며 d는 두 교차로간의 거리이다. 도로는 양방향 도로이다. s, e( 0 ≤ s, e < M && s ≠ e), d( 1 ≤ d < 2147483647) 이나 간선의 총합은 정수 범위 이내이다.
출력
시민의 안전을 최소한으로 보장하면서 전기를 절약할 때, 절약할 수 있는 최대 금액을 출력하시오.
예제
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
51
출처
Ulm Local 2009
로그인해야 코드를 작성할 수 있어요.