레이팅 미적용당신이 바르샤바의 관광객이고, 시외의 놀라운 명소를 보러 가는 버스 투어를 예약했다고 하자. 버스는 먼저 (바르샤바는 큰 도시라 꽤 오랫동안) 시내를 돌며 각 호텔에서 사람들을 태운다. 그런 다음 놀라운 명소로 가고, 몇 시간 뒤 다시 시내로 돌아와 각 호텔에 들르며 이번에는 사람들을 내려 준다. 어째서인지 당신이 이렇게 할 때마다 항상 당신의 호텔이 승차 때는 첫 번째로, 하차 때는 마지막으로 방문된다. 즉, 그리 놀랍지 않은(n\(ot-so-am\)azing) 지역 호텔 관광을 두 번이나 견뎌야 한다는 뜻이다. (어떤 이유로 호텔을 정말 좋아하는 게 아니라면) 이는 분명 당신이 원하는 바가 아니니, 고쳐 보자. 관광 회사가 버스 투어 노선을 더 공정하게 짤 수 있도록 하는 소프트웨어를 개발할 것이다. 모두의 총 이동 거리가 더 길어질 수도 있지만, 공정한 건 공정한 거니까. 이 문제에는 출발 위치(관광 회사 본사), 승하차를 위해 방문해야 하는 \(h\)개의 호텔, 그리고 목적지(놀라운 명소)가 있다. 본사에서 출발해 모든 호텔을 거쳐 명소로 가고, 다시 (다른 순서일 수도 있는) 모든 호텔을 거쳐 마지막으로 본사로 돌아오는 경로를 찾아야 한다. (특히 당신을 포함한) 어떤 관광객도 호텔 관광 전체를 두 번 견디도록 강요받지 않게 하기 위해, 명소로 가는 길에 처음 ⌊\(h/2\)⌋개 안에 방문되는 모든 호텔은 돌아오는 길에도 처음 ⌊\(h/2\)⌋개 안에 방문되어야 한다. 이 제한을 지키면서 전체 버스 투어를 가능한 한 짧게 만들고자 한다. 이 제한 때문에 버스가 어떤 호텔 앞을 정차하지 않고 지나친 뒤(이는 방문으로 간주하지 않는다) 나중에 방문해야 할 수도 있음에 유의하라. 첫 번째 샘플 입력이 이를 보여 준다.
각 테스트 케이스의 첫 줄에는 \(3 \le n \le 20\), \(2 \le m\)을 만족하는 두 정수 \(n\)과 \(m\)이 주어진다. \(n\)은 위치(호텔, 본사, 명소)의 수이고 \(m\)은 버스가 오갈 수 있는 위치 쌍의 수이다. \(n\)개의 서로 다른 위치에는 0부터 \(n - 1\)까지 번호가 붙어 있는데, 0은 본사, 1부터 \(n - 2\)까지는 호텔, \(n - 1\)은 명소이다. 어떤 위치 쌍 사이에도 직접 연결은 최대 하나이며, 어떤 위치에서든 다른 어떤 위치로도 (직접은 아닐 수 있지만) 이동할 수 있다고 가정한다. 첫 줄 다음에는 \(m\)개의 줄이 이어지며, 각 줄에는 \(0 \le u\), \(v \le n - 1\), \(u\)̸ = \(v\), \(1 \le t \le 3600\)을 만족하는 세 정수 \(u\), \(v\), \(t\)가 주어진다. 이는 버스가 위치 \(u\)와 \(v\) 사이를 (어느 방향으로든) \(t\)초에 직접 이동할 수 있음을 나타낸다.
각 테스트 케이스마다 케이스 번호와 가능한 가장 짧은 투어의 시간(초)을 출력한다.
5 4
0 1 10
1 2 20
2 3 30
3 4 40
4 6
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
Case 1: 300
Case 2: 6