解决交通拥堵对于年轻的城市规划师来说是一个困难的挑战。数以百万计的司机，每个人都有不同的目标并做出独立的决策，共同构成了一个复杂的系统，其行为有时可以预测，有时却十分混乱。作为一名敬业的公务员，你的任务是优化一系列道路上的早高峰交通。

所有道路都位于一个住宅区和一个市中心商业区之间。早上，居住在住宅区的每个人都会开车前往商业区。任何特定道路上的早高峰通勤流量都只朝一个方向行驶，且所有路径均无环（早晨出行的司机不会走回头路）。

每条道路都需要一定的行驶时间，因此某些路线会比其他路线更快。司机更有可能选择更快的路线，从而导致这些道路出现拥堵。为了尽可能平衡交通，你需要在某些道路上加收过路费，使得每条路线的最终感知“成本”相同。然而，为了避免给司机带来太多困扰，无论司机选择哪条路线，都不能对其重复收费（即任何路线最多只能包含一条收费道路）。

图 5 展示了由五条道路组成的网络，它们构成了从住宅区（交叉口 1）到市中心商业区（交叉口 4）的路线。每条道路的行驶成本用蓝色大字标出。虚线箭头表示从 1 到 4 的三条可能路线。起初，这些路线的成本分别为 10、8 和 12。在连接 1 和 4 的道路上增加 2 的过路费，并在连接 3 和 4 的道路上增加 4 的过路费后，每条路线的成本都变为了 12。

图 5：连接交叉口 1 的住宅区与交叉口 4 的商业区的道路

你必须确定哪些道路应该收费以及每笔过路费应该是多少，使得从起点到终点的每条路线都具有相同的成本（行驶时间成本 + 可能的过路费），且任何路线都不包含超过一条收费道路。此外，选择的过路费应当使最终的路线成本最小。在某些情况下，可能无法施加满足上述条件的过路费。

输入格式

输入包含多个测试用例。

每个测试用例的第一行包含两个整数 $N$（$2 \le N \le 50000$）和 $R$（$1 \le R \le 50000$），其中 $N$ 是道路交叉口的数量，$R$ 是道路的数量。

接下来的 $R$ 行中，每行包含三个整数 $x_i$、$y_i$ 和 $c_i$（$1 \le x_i, y_i \le N$，$1 \le c_i \le 1000$），表示早高峰交通沿着第 $i$ 条道路从交叉口 $x_i$ 行驶到交叉口 $y_i$，其基础行驶时间成本为 $c_i$。

交叉口 1 是起点住宅区，交叉口 $N$ 是终点商业区。道路按输入的给定顺序从 1 到 $R$ 进行编号。每个交叉口都是从 1 到 $N$ 的某条路线的一部分，且图中无环。

最后一个测试用例之后是一行，包含两个零。

输出格式

对于每个测试用例，输出一行。

如果存在解，输出格式为 Case X: T C，其中 X 是测试用例编号（从 1 开始），T 是需要收费的道路数量，C 是每条路线的最终成本。接下来的 $T$ 行中，每行输出道路编号 $i$ 和施加在该道路上的正数过路费。

如果无解，则输出 Case X: No solution。

如果存在多个使最终成本最小的方案，输出其中任意一个即可。请遵循样例输出的格式。

样例

输入样例 1

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

输出样例 1

Case 1: 2 12 
4 2 
5 4 
Case 2: No solution