Alice 和 Bob 正在一个布满洞穴和单向通道的古老迷宫中行走。他们想要从洞穴 1 前往洞穴 $n$。所有的通道都很难通过。通道太小，无法容纳两人同时通过，并且通过一次通道会使下一个人通过该通道变得更加困难。我们定义 $d_i$ 为第 $i$ 条通道第一次通过时的难度，$a_i$ 为第二次通过时增加的难度（例如，第二个人的难度为 $d_i + a_i$）。

你的任务是为 Alice 和 Bob 找到两条（可能相同）路径，使得他们的总难度最小。

例如，在图 1 中，Alice 和 Bob 的最优解都是 1->2->4，但在图 2 中，Alice 使用 1->2->4 而 Bob 使用 1->3->4 会更好。

输入格式

最多有 200 组测试数据。每组数据以两个整数 $n, m$ ($1 \le n \le 500, 1 \le m \le 2000$) 开头，分别表示洞穴和通道的数量。接下来的 $m$ 行，每行包含四个整数 $u, v, d_i$ 和 $a_i$ ($1 \le u, v \le n, 1 \le d_i \le 1000, 0 \le a_i \le 1000$)。注意，连接同一对洞穴之间可能存在多条通道，甚至存在连接洞穴自身的通道。

输出格式

对于每组测试数据，输出案例编号和最小总难度。

样例

输入 1

4 4
1 2 5 1
2 4 6 0
1 3 4 0
3 4 9 1
4 4
1 2 5 10
2 4 6 10
1 3 4 10
3 4 9 10

输出 1

Case 1: 23
Case 2: 24