문제 155
그래프를 두 부분으로 나누기
정점이 $N$개이고 간선이 $M$개인 무방향 그래프가 주어진다. 정점의 번호는 $0$부터 $N-1$까지이며, 간선의 가중치는 음이 아닌 정수이다. 그래프가 연결되어 있지 않을 수도 있으며, 자기 루프는 없고 중복 간선은 있을 수 있다.
모든 정점을 비어 있지 않은 두 집합으로 나눌 때, 서로 다른 집합을 잇는 간선의 가중치 합의 최솟값을 구해 보자.
입력
첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 100)$
각 테스트 케이스의 첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 200; 0 \le M \le 200\,000)$
두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 양 끝 정점 번호 $u$, $v$와 가중치 $w$가 공백으로 구분되어 주어진다. $(0 \le u, v < N; u \ne v; 0 \le w \le 10^6)$
전체 테스트 케이스에서 $N$의 합은 $500$ 이하이고 $M$의 합은 $300\,000$ 이하이다.
출력
각 테스트 케이스마다 서로 다른 집합을 잇는 간선의 가중치 합의 최솟값을 한 줄에 출력한다.
예제 입력 1
3 5 6 0 1 3 0 2 4 0 4 1 1 2 3 1 3 5 2 4 0 6 6 0 2 3 1 2 4 1 3 2 1 4 2 2 4 0 3 5 4 4 1 0 1 0
예제 출력 1
1 2 0