P13294 [GCJ 2013 #2] Ticket Swapping

这座城市新建成了第一条地铁线，共有 $N$ 个车站，并引入了一种新的计费方式。乘客不再只需购买一张票随意乘车，而是基于进站卡来计费。 当乘客进入地铁时，会领取一张进站卡，卡上标明了乘客进站的车站编号。当乘客出站时，需交回进站卡，并根据进站卡上标明的进站站点与实际出站站点之间的距离（即经过的车站数）计费，具体计费方式如下： * 若进出站为同一车站，不收费； * 若进出站为相邻车站，收费 $N$ 英镑； * 若间隔 $2$ 个车站，则收费 $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$ 的进站卡，相当于免费出站；第二个人在 $C$ 下车时交回写有 $A$ 的进站卡，相距 $5$ 站，收费为 $5N-10$，城市因此损失 $6$ 英镑。 现在城市想知道，如果这种行为普遍发生，他们最多可能损失多少钱。我们只考虑同一方向（从车站 $1$ 到车站 $N$，依次经过所有车站）的一趟列车。假设一名乘客从 $o$ 站到 $e$ 站，会在 $o$ 站领取进站卡，可以在 $o$ 到 $e$ 之间的任意位置与其他乘客交换进站卡（包括与在 $o$ 下车或在 $e$ 上车的人交换），然后在 $e$ 站下车时交回一张进站卡（必须交卡才能出站）。假设乘客在此期间不会中途下车（即不会交卡再重新领卡）。 给定所有乘客的出发和终点信息（每一对出发、终点及人数），请你计算在所有人都最大化交换进站卡以使城市损失最大时，城市可能遭受的总损失。

输入的第一行为测试用例数 $T$。接下来是 $T$ 组测试数据。每组测试数据第一行为车站数 $N$ 和出发-终点对数 $M$。接下来 $M$ 行，每行三个数：出发站 $o_i$，终点站 $e_i$，以及该线路上人数 $p_i$。

对于每个测试用例，输出一行 `"Case #$x$: $y"`，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 为由于换卡导致城市可能遭受的最大损失，对 $1000002013$ 取模。

**样例说明** 第一个测试用例即题面描述中的例子——两名乘客在车站 $3$ 会面并交换了进站卡。第二个测试用例中，两组乘客没有会面机会，因此无法交换进站卡（城市没有损失）。第三个测试用例中，只有一部分早下车的乘客可以和后上车的乘客交换进站卡。 **限制条件** - $1 \leq T \leq 20$ - $1 \leq o_i < e_i \leq N$ **小数据集（8 分，测试集 1 - 可见）** - $2 \leq N \leq 100$ - $1 \leq M \leq 100$ - $1 \leq p_i \leq 100$ **大数据集（11 分，测试集 2 - 隐藏）** - $2 \leq N \leq 10^9$ - $1 \leq M \leq 1000$ - $1 \leq p_i \leq 10^9$ 翻译由 ChatGPT-4.1 完成。