어린이

문제 정보

문제

호주로 여행간 어린이는 새로운 것을 많이 구경하고 싶다.



해질 무렵, 어린이는 오늘 여행의 마지막 코스로 오페라 하우스에 가려고 한다.

그리고 오페라 하우스에서 관람을 마치면 예약된 호텔로 이동할 예정이다.



새로운 것을 많이 구경하고 싶은 어린이는 같은 길을 두 번 가고 싶지 않다.

어린이에게 현재 위치에서 오페라 하우스를 지나 호텔로 가는 가장 빠른 길의 거리를 알려주자.



힌트 : 같은 정점은 두 번 이상 지나갈 수 있다.

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. ( T <= 40 )

각 테스트 케이스의 첫째 줄에는 정점의 개수 N과 길의 개수 E가 주어진다.

다음 E개 줄에 각각 하나씩 길에 대한 정보가 주어진다.

길에 대한 정보는 그 길이 연결하는 두 정점의 번호 v1, v2와 거리를 의미하는 정수 d로 구성된다.



1번 정점이 현재 위치, 2번 정점이 오페라 하우스, N번 정점이 호텔의 위치다.



3 <= N <= 100, 2 <= E <= 2000

1 <= v1, v2 <= N

1 <= d <= 100



각 테스트 케이스 사이에는 빈 줄이 하나씩 들어간다.

출력

현재 위치에서 오페라 하우스에 들린 후, 호텔로 가는 가장 빠른 길의 거리를 출력한다.

물론 같은 길을 두 번 이상 지나가지 않는다.

예제 입력

2
4 4
1 3 2
2 3 1
3 4 3
2 4 5

5 8
2 3 1
3 4 2
4 5 3
2 4 4
1 4 5
1 5 6
2 5 8
3 1 8

예제 출력

8
15

노트

3개의 댓글이 있습니다.