구급차 운행

도시 곳곳에 흩어져 있는 환자를 병원으로 옮겨야 하는 구급차가 한 대 있다. 구급차에는 환자를 최대 세 명까지 태울 수 있고, 환자를 내리려면 병원으로 돌아와야 한다. 환자를 태우거나 내리는 데 걸리는 시간은 0이다.

도시는 교차로와 도로로 이루어져 있다. 교차로 하나에 병원이 있고, 나머지 교차로마다 환자가 한 명씩 기다린다. 도로는 모두 양방향이고, 도로마다 한쪽 끝에서 반대쪽 끝까지 달리는 데 걸리는 시간이 분 단위로 정해져 있다. 어느 방향으로 달려도 시간은 같다. 구급차는 처음에 병원에 있다.

환자가 없는 교차로나 이미 지나간 교차로를 몇 번이든 다시 지나가도 된다. 모든 환자를 병원으로 옮기는 데 필요한 최소 시간을 구하라. 마지막 환자를 내린 뒤 구급차는 병원에 있어야 한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 환자가 있는 교차로의 수 $N$과 도로의 수 $M$이 주어진다. 이어지는 $M$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $c_i$가 주어진다. 교차로 $a_i$와 $b_i$를 잇는 양방향 도로가 있고, 그 도로를 달리는 데 $c_i$분이 걸린다는 뜻이다.

도시의 교차로는 모두 $N + 1$개이고 0번부터 $N$번까지 번호가 붙어 있다. 병원은 $N$번 교차로에 있고, 환자는 0번부터 $N - 1$번까지의 교차로에 한 명씩 있다.

• $0 < T \le 100$
• $1 \le N \le 20$
• $M > 0$
• $0 \le a_i, b_i \le N$
• $0 < c_i \le 100000$
• 어떤 두 교차로 사이에도 이동 경로가 항상 존재한다.
• 두 교차로를 잇는 도로는 많아야 한 개다.

각 테스트 케이스마다 모든 환자를 병원으로 옮기는 데 필요한 최소 시간을 분 단위로 한 줄에 출력한다.