문제 설명
주어진 가중치 무방향 그래프에서 최소신장트리를 구하여 주세요.
입력 설명
첫 줄에는 테스트케이스 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)은 간선의 가중치 값입니다. 각 테스트케이스에 주어지는 그래프는 연결 그래프입니다.
출력 설명
각 테스트케이스마다 주어진 가중치 무방향 그래프의 최소신장트리를 구하고, 그 트리의 모든 간선의 합을 출력하여 주세요.
1
5 7
0 1 4 0 2 2 1 2 3 1 3 5 1 4 1 2 3 6 3 4 7