#1371 JongMan's Honeymoon

25  3 s   128 MB  

Description

7월 11일에 결혼을 하고 신혼 여행을 유럽으로 가기로 한 종만은 신혼 여행 일정을 다음 규칙에 따라 세우기로 했습니다.

종만은 신혼 여행 일정을 직접 짜고 싶었지만, 결혼 준비로 아주 바쁘기 때문에 일단 당신에게 신혼 여행을 하는데 필요한 비용이 얼마나 되는지 알아봐달라고 부탁했습니다. 당신은 종만을 도와서 신혼 여행을 위해 필요한 비용을 알아낼 수 있는 프로그램을 만들어야 합니다.

Input

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50)가 주어집니다. 각각의 테스트 케이스의 첫 줄에는 도시의 개수 N (3 <= N <= 100) 과 도시 간의 이동 방법의 수 M (2 <= M <= N(N+1)/2) 이 주어집니다. 이후 M 줄에는 각 3개의 정수로 두 도시의 번호 c1, c2와 이동하는데 드는 비용 e가 주어집니다. (0 <= c1, c2 < N, 1 <= e <= 100) 입력으로 주어지는 도시 중 0번 도시는 런던, 1번 도시는 파리, 2번 도시는 프라하입니다.

Output

각각의 테스트 케이스에 대해 종만이 정한 규칙을 만족하는 경로의 최소 비용을 출력합니다.

Sample Input

Sample Output

2
4 5
0 2 5
0 3 3
1 2 4
1 3 2
2 3 1
5 8
0 1 6
0 3 8
0 4 5
1 2 8
1 4 3
2 3 1
2 4 4
3 4 2
8
16