JongMan's Honeymoon

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

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

  1. 같은 도시는 두 번 방문하지 않는다.
  2. 출발지는 런던, 마지막 도착지는 파리가 되도록 한다.
  3. 2004년 애증의 장소인 프라하는 반드시 방문한다.
  4. 도시간의 이동에는 생각보다 많은 돈이 들기 때문에 최소한의 비용으로 이동하는 경로를 선택하도록 한다.

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

입력

입력의 첫 줄에는 테스트 케이스의 수 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번 도시는 프라하입니다.

  • 모든 경로는 양방향 통행이 가능합니다.
  • 종만이 정한 규칙을 만족하는 경로가 존재하지 않는 테스트 케이스는 들어오지 않습니다.
  • 두 도시 사이 간에 두 가지 이상의 이동 방법이 있는 경우는 없습니다.

출력

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

예제 입력

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

노트

1개의 댓글이 있습니다.