2023 T4 旅游巴士

主知识点：搜索与图论。交叉标签：图论、最短路、状态扩展。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 bus.in / bus.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

一个景区有 $n$ 个地点和 $m$ 条单向道路，每条通过用时为 1。地点 1 为入口，地点 $n$ 为出口。时刻 0 起，每隔 $k$ 时间单位有巴士到入口，也有巴士离开出口，因此入园与离园时间都必须为非负的 $k$ 的倍数。

道路 $i$ 有开放时刻 $a_i$，开始通过不能早于该时刻。入园后只能连续沿道路移动，在地点或道路均不能等待，也可以重复走道路。求能够乘巴士离开的最早时刻；无法离开则输出 -1。

输入格式

输入的第一行包含 $3$ 个正整数 $n, m, k$，表示旅游景点的地点数、道路数，以及旅游巴士的发车间隔。

输入的接下来 $m$ 行，每行包含 $3$ 个非负整数 $u _ i, v _ i, a_ i$，表示第 $i$ 条道路从地点 $u _ i$ 出发，到达地点 $v _ i$，道路的“开放时间”为 $a _ i$。

输出格式

输出一行，仅包含一个整数，表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案，输出 -1。

样例

样例 1

输入：

5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1

输出：

6

数据范围与特殊性质

对于所有测试数据有：$2 \leq n \leq 10 ^ 4$，$1 \leq m \leq 2 \times 10 ^ 4$，$1 \leq k \leq 100$，$1 \leq u _ i, v _ i \leq n$，$0 \leq a _ i \leq 10 ^ 6$。

测试点编号	$n \leq$	$m \leq$	$k \leq$	特殊性质
$1 \sim 2$	$10$	$15$	$100$	$a _ i = 0$
$3 \sim 5$				无
$6 \sim 7$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	$a _ i = 0$
$8 \sim 10$				无
$11 \sim 13$			$100$	$a _ i = 0$
$14 \sim 15$				$u _ i \leq v _ i$
$16 \sim 20$				无

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P9751
• 赛事：CSP-J 第二轮入门级 2023。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。