출처 : SW Expert Academy (https://swexpertacademy.com)

출처 : SW Expert Academy (https://swexpertacademy.com)


문제 내용 : 간선 비용이 있는 무방향 그래프에서 각 노드별 최단 경로로만 다닐수 있는 석환이가 모든 노드를 청소할때 드는 청소비용을 구해라.
한번 청소하면 다시 청소할 필요 없다. 청소 비용은 간선의 가중치와 같다. 석환이네 집은 1번노드.

[입력]

첫 줄에 테스트케이스의 개수 T가 주어진다. (T ≤ 20)

각 테스트케이스의 첫째 줄에 건물의 수를 나타내는 자연수 N과 길들의 수를 나타내는 자연수 M이 주어진다 (1 ≤ N ≤ 200,000, 0 ≤ M ≤ 500,000).

다음 이어지는 M개의 줄 각각에는 하나의 길을 나타내는 3개의 자연수가 주어진다.

그 중 첫 두 수는 서로 다른 건물의 번호이고 세 번째 수는 그 길의 길이 이다.

각 길의 길이는 1이상 10억 이하이다.

동일한 쌍의 건물을 잇는 길은 최대 하나이다.

모든 건물 사이에 길들을 이용해서 이동할 수 있는 경로가 존재한다.

[출력]

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 석환이 청소 비용의 최소값을 출력한다.



출처 : SW Expert Academy (https://swexpertacademy.com)