문제1204--가중치 무방향 그래프에서 최소신장트리 구하기

1204: 가중치 무방향 그래프에서 최소신장트리 구하기

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

주어진 가중치 무방향 그래프에서 최소신장트리를 구하여 주세요. 

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=1,000)가 주어집니다. 각 테스트케이스마다 첫 줄에는 그래프를 구성하는 노드의 수 N(1<=N<=100), 그래프를 구성하는 간선의 수 E(0<=E<=N(N-1)/2)가 주어집니다. 그다음 줄에는 E개의 간선 정보가 주어집니다. 각 간선마다 3개의 정수 a, b, c가 주어집니다. a(0<=a<=N-1)는 간선의 시작 노드이고,  b(0<=b<=N-1)는 간선의 끝 노드이며, c(1<=c<=50)은 간선의 가중치 값입니다. 각 테스트케이스에 주어지는 그래프는 연결 그래프입니다.

출력 설명

각 테스트케이스마다 주어진 가중치 무방향 그래프의 최소신장트리를 구하고, 그 트리의 모든 간선의 합을 출력하여 주세요.

입력 예시 Copy

1
5 7
0 1 4 0 2 2 1 2 3 1 3 5 1 4 1 2 3 6 3 4 7

출력 예시 Copy

11

출처/분류