这座城市修建了第一条地铁线路，总共有 $N$ 个车站，并引入了一种新的乘车付费方式。乘客不再是购买单程票进行任意行程，而是根据“入站卡”付费。

当乘客进入地铁时，每位乘客会领取一张“入站卡”，上面标明了乘客进入的车站。当离开地铁时，乘客必须交出入站卡，并根据入站卡上标明的入站车站与交卡时的出站车站之间的距离（以经过的站数计）支付费用。 费用计算规则如下：

• 如果是同一车站，则无需付费；
• 如果是相邻车站，则支付 $N$ 英镑；
• 如果距离为两站，则支付 $2N - 1$：第一站收费 $N$，第二站收费 $N - 1$；
• 第三站收费 $N-2$（因此三站行程总共支付 $3N - 3$），第四站收费 $N-3$，第 $i$ 站收费 $N + 1-i$；
• 因此，如果从地铁的一端坐到另一端（距离为 $N-1$ 站），最后一段路程支付 2 英镑，总共支付 $(N^2 + N - 2) / 2$ 英镑。

系统引入后，城市发现收益未达预期。他们推测这可能是因为乘客交换了入站卡——例如，如果一个人在车站 $A$ 进入，坐两站到 $B$ 出站，而另一个人在 $B$ 进入，坐三站到 $C$ 出站，他们通常总共支付 $2N - 1 + 3N - 3 = 5N - 4$。但如果两人在车站 $B$ 交换了入站卡，那么第一个人将免费乘车（因为他在 $B$ 站出站时交出的是标明 $B$ 站的入站卡，距离为零）；而第二个人在 $C$ 站出站时交出的是标明 $A$ 站的入站卡，距离为 5 站，需支付 $5N - 10$，城市净损失 6 英镑！

城市现在想知道，如果这种做法普及，他们可能面临的最大损失是多少。我们仅考虑地铁的一个方向（从车站 1 到车站 $N$，按顺序经过所有车站），且该线路上只有一列火车。我们假设从 $o$ 到 $e$ 的乘客在 $o$ 处获得一张入站卡，可以在 $o$ 到 $e$ 之间的任何地方与任何其他乘客交换入站卡（包括与在 $o$ 处下车或在 $e$ 处上车的乘客交换），最后在 $e$ 处持某张入站卡出站（出站必须交出一张入站卡）。我们还假设乘客中途不会下车（即不会交出当前持有的卡并获取新卡）。

给定一份交通流量图（指定有多少乘客从哪一站坐到哪一站），请计算城市可能遭受的财务损失，假设乘客通过交换卡片来最大化这一损失。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含车站数量 $N$（车站编号为 1 到 $N$），以及给定的起点-终点对数量 $M$。接下来的 $M$ 行每行包含三个数字：起点站 $o_i$、终点站 $e_i$ 和乘客数量 $p_i$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是城市因票务交换可能观察到的总损失，对 1000002013 取模。

数据范围

$1 \le T \le 20$ $1 \le o_i < e_i \le N$

小数据集（测试集 1 - 可见；8 分）

$2 \le N \le 100$ $1 \le M \le 100$ $1 \le p_i \le 100$

大数据集（测试集 2 - 隐藏；11 分）

$2 \le N \le 10^9$ $1 \le M \le 1000$ $1 \le p_i \le 10^9$

样例

样例输入 1

3
6 2
1 3 1
3 6 1
6 2
1 3 2
4 6 1
10 2
1 7 2
6 9 1

样例输出 1

Case #1: 6
Case #2: 0
Case #3: 10

说明

第一个测试用例是题目描述中的情况——两名乘客在 3 号站相遇并交换了车票。在第二个测试用例中，两名乘客根本没有相遇，因此他们无法交换车票（所以城市没有损失）。在第三个测试用例中，只有一名早期乘客能与后期乘客交换车票。