想象一下，你是一位在华沙的游客，预订了一次巴士旅行，去参观城外的一个绝佳景点。巴士首先会在城里绕行一段时间（由于华沙是一座大城市，这需要很长时间），在各自的酒店接上游客。然后，它会前往那个绝佳景点，并在几个小时后返回城里，再次开往每家酒店，这次是为了送游客下车。

出于某种原因，每当你这样做时，你的酒店总是第一个被接载，也是最后一个被送达的，这意味着你必须忍受两次并不怎么样的酒店观光之旅。这显然不是你想要的（除非你出于某种原因真的很喜欢酒店），所以让我们来解决这个问题。我们将开发一些软件，使观光公司能够更公平地规划其巴士路线——尽管这有时意味着每个人的总路程会变长，但公平就是公平，对吧？

对于这个问题，有一个起始位置（观光公司总部）、$h$ 家需要接送的酒店，以及一个目的地（绝佳景点）。我们需要找到一条路线，从总部出发，经过所有酒店，到达景点，然后再次经过所有酒店（可能顺序不同），最后回到总部。为了保证没有游客（特别是你）被迫忍受两次完整的酒店观光，我们要求在前往景点的途中，前 $\lfloor h/2 \rfloor$ 家被访问的酒店，也必须在返回途中前 $\lfloor h/2 \rfloor$ 家被访问的酒店中。在满足这些限制的前提下，我们希望使整个巴士行程尽可能短。请注意，这些限制可能会迫使巴士在不停车的情况下经过一家酒店（这不被视为访问），然后再在稍后访问它，正如第一个样例输入中所说明的那样。

输入格式

每个测试用例的第一行包含两个整数 $n$ 和 $m$，满足 $3 \le n \le 20$ 和 $2 \le m$，其中 $n$ 是地点（酒店、总部、景点）的数量，$m$ 是巴士可以行驶的地点对的数量。

$n$ 个不同的地点编号从 $0$ 到 $n-1$，其中 $0$ 是总部，$1$ 到 $n-2$ 是酒店，$n-1$ 是景点。假设任意一对地点之间最多只有一条直接连接，并且可以从任何地点到达任何其他地点（但不一定直接到达）。

第一行之后是 $m$ 行，每行包含三个整数 $u$、$v$ 和 $t$，满足 $0 \le u, v \le n-1$，$u \neq v$，$1 \le t \le 3600$，表示巴士可以在 $t$ 秒内直接在地点 $u$ 和 $v$ 之间行驶（双向）。

输出格式

对于每个测试用例，显示用例编号和最短行程的时间（以秒为单位）。

样例

输入 1

5 4
0 1 10
1 2 20
2 3 30
3 4 40

输出 1

Case 1: 300

输入 2

4 6
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1

输出 2

Case 2: 6