题目描述

给出一个 $n$ 个点 $m$ 条有向边的有向图。初始时间为 $0$ 。求：从点 $1$ 出发到点 $n$ 的最早时刻（没有方案则输出 $−1$）。

限制条件如下：
1、从点 $1$ 出发的时间 必须是 k 的倍数。
2、每条边的边权 $a_i$ 不是表示通过该边的时间，而是表示只有在当前时间 $\ge a_i$ 时才可以通过，通过任何一条边的时间为1。
3、任何时刻都不能在原地不动，即每一个时间点必须走一条边。

输入格式

第一行包含 3 个正整数 $, m, k$（$2 \leq n \leq 10 ^ 4$，$1 \leq m \leq 2 \times 10 ^ 4$，$1 \leq k \leq 100$）。
接下来 $m$ 行，每行包含 3 个非负整数 $u_i, v_i, a_ i$，表示第 $i$ 条边从点 $u _ i$ 出发，到达地点 $v _ i$，允许通过的时间必须 $\ge a_i$（$0 \leq a_i \leq 10 ^ 6$）。

输出格式

输出一行，仅包含一个整数，表示最早到达 点 $n$ 的时刻。如果不存在符合要求的方案，输出 -1。

样例 #1

样例输入 #1

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

样例输出 #1

5

【样例 #1 解释】

可以在 $3$ 时刻到达 $1$，沿 $1 \to 2 \to 5$ 的顺序走到 $n$，并在 $5$ 时刻离开。