星穹列车
Description
星穹列车是穿梭于星系之间的神秘交通工具。 整个星系可以视作一个有 n 个星球、m 条航线的有向图。每条航线 连接两个星球，表示星穹列车可以从一个星球跃迁到另一个星球，跃迁所需的时间已知且固定。星穹列车的跃迁依赖于星球上的星门，只有在星门开启时，列车才能 从该星球出发，沿着特定的航线跃迁至下一个目的地。然而，即使星门处于关闭状态，星穹列车也可以正常抵达该星球。 每个星球上的星门会周期性地开启和关闭。第 i 个星球的星门开启 时间由 l𝑖, r𝑖,t𝑖（0 ≤ l𝑖 ≤ r𝑖 < t𝑖） 决定，表示星门以周期 t𝑖进行 循环，且仅在每个周期的 [l𝑖, r𝑖] 时间段内开启。 当星穹列车从停止状态进入跃迁状态时，需要耗费 k 时间，并且只有在当前星球的星门开启时才能出发。（列车只需要在退出停止状态的那一时刻，星门处于开启状态） 例如，列车在时刻 T 选择了航线 (u, v, w) 并从停止状态出发。那么需要在时刻 T 时，星球 u 的星门处于开启状态，且列车会在时刻 T + k 进入跃迁状态，沿着航线跃迁至星球 v，并在时刻 T + k + w 到达。 当星穹列车到达某个星球后，有以下两种选择： 停止：退出跃迁状态，在星门开启时可以从停止状态再次出发。 继续跃迁：不退出跃迁状态，沿航线继续前进。但此时这个星球的星门必须处于开启状态。 星穹列车从起点星球 1 出发，初始状态为停止，初始时间为 0（对 于所有星门，都是循环周期的 0 时刻）。请计算从起点星球到达每个 星球所需的最短时间。
Format
Input
第一行包含三个整数 n, m, k，分别表示星球的数量、航线的数量，以 及进入跃迁状态需要耗费的时间。 接下来 m 行，每行包含三个整数 u𝑖, v𝑖, w𝑖，代表从 u𝑖 到 v𝑖需要花 费 w𝑖 的时间。 接下来 n 行，每行包含三个整数 l𝑖, r𝑖,t𝑖，表示第 i 个星球的星门开启时间段和循环周期。
Output
输出一行，包含 n 个用空格分隔的整数，依次表示从起点星球 1 出 发，到达每个星球所需的最短时间。 保证从起点出发可达所有点。
Samples
样例1
3 2 10
1 2 1
2 3 1
1 1 2
3 4 10
1 4 5
0 12 15
样例1说明： 在第一个样例中，1 的可出发时间是 1、3、5、 …， 2 的可出发时间是 3、4、13、14、. .. 从点 1 到点 2 的最短时间是在时刻 1 从点 1 出发到点 2，花费 1 + 10 + 1 = 12。即：列车一开始位于点 1，列车在时刻 1 时退 出停止状态，在时刻 11 时进入跃迁状态，在时刻 12 时到达点 2。 从点 1 到点 3 的最短时间是在时刻 3 从点 1 出发到点 2，到达点 2 传送门仍然开着，可以继续前往点 3，花费 3 + 10 + 1 + 1 = 15
样例2
6 6 10
1 2 1
2 3 1
3 2 1
2 4 1
4 5 1
5 6 1
0 0 10
0 1 2
0 1 2
4 4 6
2 2 7
0 1 2
0 11 12 12 17 24
样例2说明： 在第二个样例中， 点 1 到点 2 的最短时间是在时刻 0 从点 1 出发到点 2，花费 10 + 1 = 11 点 1 到点 3 的最短时间是在时刻 0 从点 1 出发到点 2 再到点 3， 花费 10 + 1 + 1 = 12 点 1 到点 4 的最短时间是在时刻 0 从点 1 出发到点 2 再到点 4， 花费 10 + 1 + 1 = 12 点 1 到点 5 的最短时间是在时刻 0 从点 1 出发到点 2，然后开始 在点 2 和点 3 绕圈，在时刻 15 从点 2 出发到点 4 再到点 5， 花费 15 + 1 + 1 = 17。 点 1 到点 6 的最短时间是在时刻 0 从点 1 出发到点 2，然后开 始在点 2 和点 3 绕圈，在时刻 21 从点 2 出发到点 4 再到点 5再到点 6，花费 21 + 1 + 1 + 1 = 24
样例3
6 5 2
1 2 3
2 3 1
3 4 1
4 5 1
5 6 1
0 0 10
0 1 2
0 0 3
0 0 5
1 1 10
0 1 2
0 5 6 7 11 12
样例3说明： 第三个样例中， 到点 2 的最短时间是在时刻 0 从点 1 出发到点 2，花费 2 + 3 = 5 到点 3 的最短时间是在时刻 0 从点 1 出发到点 2 到点 3，花费 2 + 3 + 1 = 6 到点 4 的最短时间是在时刻 0 从点 1 出发到点 2 到点 3 到点 4，花费 2 + 3 + 1 + 1 = 7 到点 5 的最短时间是在时刻 0 从点 1 出发到点 2，然后停止，等 到时刻 6 再出发到点 3 到点 4 到点 5，花费 6 + 2 + 1 + 1 + 1 = 11 到点 6 的最短时间是在时刻 0 从点 1 出发到点 2，然后停止，等 到时刻 6 再出发到点 3 到点 4 到点 5 到点 6，花费 6 + 2 + 1 + 1 + 1 + 1 = 12
Limitation
对于所有测试数据，保证： 2 ≤ n, m ≤ 5000 0 ≤ k ≤ 103 1 ≤ u𝑖, v𝑖≤ n，保证没有重边和自环。 1 ≤ w𝑖 ≤ 103 0 ≤ l𝑖 ≤ r𝑖 < t𝑖 2 ≤ t𝑖≤ 10 保证从起点出发可达所有点。 对于 30% 的测试数据，保证有 2 ≤ n, m ≤ 100 对于另外 30% 的测试数据，保证 2 ≤ n, m ≤ 1000 对于另外 20% 的测试数据，保证 k = 0
1s, 1024KiB for each test case.
相关
在下列比赛中: