문제
세일즈맨이 N개의 도시를 방문하여 업무를 수행하고자 한다. 각 도시는 0번 부터 N-1번까지 번호가 메겨져 있으며, 각 도시를 적어도 한번 이상 방문을 하려고 한다. 세일즈맨은 0번 도시에서 시작하여 어떤 도시던 마지막 방문지로 정할 수 있다.
도시들 사이에는 M개의 서로 다른 두개의 도시를 잇는 양방향 도로가 있으며, 각 도로를 이용하기 위해서는 통행 요금을 내야 한다.
세일즈맨은 타임머신을 가지고 있는데, 타임머신을 이용하여 과거에 방문했던 도시로 아무런 비용없이 돌아갈 수 있다. 또한 타임머신을 쓸 경우 시간은 소요되지 않으며, 현재의 시간이 유지된다.
예를 들어 0, 1, 2, 3, 4 순으로 도시를 방문했을 때, 현재 세일즈맨은 현재 4번 도시에 위치해 있다. 여기서 타임머신을 쓸 경우 0, 1, 2, 3, 4 중 한곳으로 돌아갈 수 있다. 만약 2번 도시로 돌아 갔을 때, 그 다음에는 0, 1번 도시로만 돌아갈 수 있고, 3, 4번 도시로는 돌아가지 못한다. 타임머신을 사용하였을 경우 시간을 완전히 거슬러 가는 것이 아니기 때문에 이미 방문했던 곳은 방문 했던 곳으로 간주하게 된다. 따라서 5번에서 2번으로 타임머신을 써서 이동을 했을 경우에도 0, 1, 2, 3, 4번 도시를 방문한것으로 인정된다.
도시의 수와 각 도로의 정보가 주어졌을 때 0번 도시에서 시작하여 모든 도시를 적어도 한번 이상 방문하기 위한 통행 요금의 최소 합을 구하는 프로그램을 작성하라.
입력
입력은 여러개의 테스트 케이스로 이뤄지며, 입력의 첫 줄에는 테스트 케이스의 수를 뜻하는 T(1≤T≤200 )이 입력된다. 각 테스트 케이스의 첫 줄에는 1이상 1,000 이하의 정수 N과 M이 주어지며, 이는 도시의 수와 도로의 수를 뜻한다. 그 다음 줄 부터 M개의 줄에는 3개의 정수 a와 b, 그리고 c가 주어지는데 a번 도시와 b번 도시를 직접 잇는 양방향 도로가 존재하며, 통행비용은 c임을 뜻한다. a와 b는 0이상 N-1이하의 정수이며, c는 1이상 10,000,000이하의 정수다.
출력
입력에 대해서 모든 도시를 방문하기 위한 최소 통행요금의 합을 구하라. 만약 모든 도시를 방문 하는 것이 불가능할 경우 -1을 출력한다.
예제
3
3 3
0 1 1
0 2 1
1 2 2
6 5
0 1 2
1 4 2
4 3 3
2 4 4
0 5 3
3 1
0 2 2
2
14
-1
로그인해야 코드를 작성할 수 있어요.