버스 기사 승재

승재는 유명한 관광 회사 ALPS에서 버스 기사로 일합니다. 승재가 하는 일은 ALPS 본사에서 버스로 출발해 $h$개의 호텔에서 관광객을 한 명씩 태우고, 그들을 모두 관광지로 데려간 뒤, 다시 각자의 호텔로 돌려보내고 ALPS 본사로 돌아오는 것입니다. ALPS가 가는 관광지는 언제나 한 곳으로 정해져 있어, 버스는 늘 그 한 곳만 들르면 됩니다.

ALPS는 서비스를 중시하기 때문에, 먼저 태운 관광객을 대체로 먼저 내려 주려고 합니다. 구체적으로, ALPS는 다음 규칙을 따릅니다. $h$개의 호텔에서 어떤 순서로 관광객을 태웠을 때, 태운 순서가 앞에서부터 $h/2$번째 이내인 관광객은 내리는 순서도 앞에서부터 $h/2$번째 이내여야 합니다.

예를 들어 관광객을 1 2 3 4 5 순서로 태웠다고 합시다. 이때 2 1 3 4 5나 1 2 5 3 4 순서로 내려 주는 것은 괜찮지만, 1 3 2 4 5 순서로 내려 주는 것은 안 됩니다. 2번째로 태운 관광객이 3번째로 내렸는데, $3$은 $5/2$보다 크기 때문입니다.

승재는 기름값을 아끼고 싶어서, 하루 동안 버스가 이동하는 전체 거리를 최소로 하고 싶습니다. ALPS 본사와 호텔들, 그리고 관광지 사이의 이동 시간이 주어질 때, 규칙을 지키면서 버스가 이동하는 전체 거리의 최솟값을 구하세요.

규칙은 태우고 내리는 순서만 정하기 때문에, 규칙을 지키면 최단 경로가 되지 않을 수도 있고, 때로는 호텔을 그냥 지나쳐야 할 수도 있습니다. 오직 규칙을 지키면서 이동 거리가 가장 짧은 경로만 구하면 됩니다.

각 테스트 케이스의 첫째 줄에는 정점의 수 $n$ ($3 \le n \le 20$)과 간선의 수 $m$ ($2 \le m$)이 주어집니다. $n$은 호텔과 관광지, 그리고 출발 지점을 모두 포함한 수입니다.

정점은 $0$번부터 $n-1$번까지 번호가 매겨집니다. $0$번 정점은 버스의 출발 지점, $n-1$번 정점은 관광지이며, $1$번부터 $n-2$번까지의 정점은 호텔을 뜻합니다.

이어서 $m$개의 줄에 세 정수 $u$, $v$, $t$ ($0 \le u, v \le n-1$, $1 \le t \le 3600$)가 주어집니다. 이는 $u$에서 $v$로 가는 데 시간 $t$가 걸린다는 뜻입니다. 길은 양방향이므로 $v$에서 $u$로 가는 데에도 시간 $t$가 걸립니다.

임의의 두 정점 사이에는 경로가 반드시 하나 이상 존재한다고 가정해도 좋습니다. 입력에는 여러 개의 테스트 케이스가 있으며, 입력의 끝까지 처리합니다.

각 테스트 케이스마다 Case t: d를 출력합니다. $t$는 테스트 케이스 번호(1부터 시작), $d$는 규칙을 만족하는 가장 짧은 이동 거리입니다.