Bus Driver Seungjae

Seungjae drives buses for the famous tour company ALPS. His job is to leave the ALPS headquarters by bus, pick up one tourist from each of the $h$ hotels, take them all to the sightseeing spot, then return every tourist to their own hotel and drive back to the ALPS headquarters. The only sightseeing spot ALPS uses is a single fixed location, so the bus always visits just that one spot.

Because ALPS prides itself on service, it tries to drop tourists off roughly in the order they were picked up. Concretely, ALPS follows this rule: when the tourists are picked up from the $h$ hotels in some order, every tourist whose pick-up position is within the first $h/2$ must also have a drop-off position within the first $h/2$.

For example, suppose five tourists are picked up in the order 1 2 3 4 5. Then dropping them off as 2 1 3 4 5, or as 1 2 5 3 4, is allowed, but dropping them off as 1 3 2 4 5 is not: the tourist picked up 2nd is dropped off 3rd, and $3$ is greater than $5/2$.

Seungjae wants to save fuel, so he wants the total distance the bus travels in a day to be as small as possible. Given the travel times between the ALPS headquarters, the hotels, and the sightseeing spot, compute the minimum possible total distance of a route that obeys the rule.

Because the rule fixes only the order of pick-ups and drop-offs, obeying it may keep the bus from taking an otherwise shorter route, and the bus may sometimes have to drive past a hotel without stopping. You only need to find the shortest route that still obeys the rule.

Each test case begins with a line containing the number of vertices $n$ ($3 \le n \le 20$) and the number of edges $m$ ($2 \le m$). Here $n$ counts the hotels, the sightseeing spot, and the starting point together.

Vertices are numbered $0$ to $n-1$. Vertex $0$ is the bus's starting point, vertex $n-1$ is the sightseeing spot, and vertices $1$ through $n-2$ are the hotels.

The next $m$ lines each contain three integers $u$, $v$, and $t$ ($0 \le u, v \le n-1$, $1 \le t \le 3600$), meaning it takes time $t$ to travel from $u$ to $v$. Roads are two-way, so travelling from $v$ to $u$ also takes time $t$.

You may assume that at least one path exists between any pair of vertices. The input contains several test cases; process them until the end of the input.

For each test case, print Case t: d, where t is the test case number (starting from 1) and d is the minimum total travel distance of a route that obeys the rule.