버스기사 승재

승재는 유명한 관광회사 ALPS(Amazing and Lovely and Perfect Sightseeing) 에서 버스기사로 일하고있다. 특히 승재가 태워주는 World Final 행 버스는 승차감이 최고인 것으로 유명하다.

승재가 하는 일은  ALPS 본사에서 버스를 타고 출발해 h개의 호텔에서 관광객들을 한 명씩 pick up 해서 관광지에 데려다 준 뒤, 그들을 다시 원래 호텔로 돌려보내고 ALPS 본사로 돌아오는 일이다. ALPS가 좋아하는 관광지는 ACM(Amazing Common Mountain) 뿐이기 때문에 관광지는 늘 ACM 한 곳만을 둘러보면 된다고 한다.

ALPS는 서비스정신이 뛰어난 회사이기 때문에, pick up을 먼저 한 관광객들부터 호텔로 돌려보내려고 노력한다. (먼저 pick up된 관광객이 남들보다 늦게 내린다면 그는 자신이 차별대우를 받고있다고 생각할 것이고, 항의가 들어온다면 ALPS는 망하게 된다.) 이에 ALPS는 자신만의 pick up 정책을 만들었다.

h개의 호텔에서 관광객들을 pick up 하는 경우, h/2번째 순서 이내로 pick up한 관광객들은 관광이 끝난 뒤 호텔로 돌려보내 줄 때도 h/2번째 순서 이내로 호텔로 돌려보내주어야 한다는 정책이다. 

(즉, 1 2 3 4 5 순서대로 pick up 했다면 돌아올 때 2 1 3 4 5 나 1 2 5 3 4 순으로 돌려보내주는 것은 가능하지만 1 3 2 4 5 순으로 돌려보내주면 안 된다. 2번째로 pick up 된 관광객이 5/2보다 큰 3번째로 내렸기 때문이다.)

승재는 버스의 기름값을 아끼고 싶기 때문에 하루동안 버스가 움직여야하는 경로의 길이를 최소로 하고 싶어졌다. ALPS 본사와 호텔들, 그리고 ACM 관광지 사이의 거리정보가 주어졌을 때, 정책을 만족하면서 버스가 움직여야하는 경로의 최솟값을 구하는 것이 이 문제이다.

정책에는 관광객을 태우고 내리는 순서만 정했기 때문에 이 정책을 지키면 최단경로가 안될 수도 있고, 어쩔때는 호텔을 그냥 지나쳐야하는 상황이 올 수도 있다. 하지만 ALPS는 그런 '사소한'것은 신경쓰지 않는다. 단지 저 정책을 지키면서 최단경로로 움직이는 데에만 집중하면 된다.

World Final 행 버스를 태운 경력이 있는 승재는 이미 답을 구하는 프로그램을 작성했다. 우리도 답을 구할 수 있음을 증명해보자.

각 케이스마다 첫째 줄에는 정점의 수 n ( 3 ≤ n ≤ 20) 과 간선의 수 m (2 ≤ m ) 이 주어진다. (n은 호텔과 관광지, 그리고 출발지점을 모두 포함한 개수이다.)

정점은 0~n-1까지 번호가 메겨지는데, 0번 정점은 버스의 출발지점이고, n-1번 정점은 관광지, 나머지 1~n-2번 정점은 호텔을 의미한다. 

이어서 m개의 줄에 세 정수 u,v,t 가 주어진다. (0 ≤ u,v ≤ n-1, 1 ≤ t ≤ 3600) 이는 u u에서 v로 가는데 t만큼의 시간이 걸린다는 것을 의미한다. 길은 양방향이기 때문에 v에서 u로 가는데에도 t만큼의 시간이 걸린다.

임의의 한 정점으로 부터 다른 임의의 정점으로 가는 경로가 반드시 하나 이상 존재한다고 가정해도 좋다.

각 케이스마다 "Case t: d" 를 출력한다. t는 케이스 번호이고, d는 조건을 만족하는 가장 짧은 경로의 이동거리이다.