有 $n$ 个点、$m$ 条有向边，每条边的通过时间均为 $1$。第 $i$ 条边在时刻 $a_i$ 开放，只有出发通过该边的时刻不小于 $a_i$ 时才能使用。

旅行者只能在 $0,k,2k,\dots$ 时刻到达点 $1$，也只能在这些时刻从点 $n$ 离开。在游览途中，旅行者不能在任何点或边上等待，但可以重复经过点和边。

求最早的离开时刻；若无解，输出 $-1$。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,a_i$，表示一条从 $u_i$ 指向 $v_i$ 的有向边。

输出格式

输出最早的离开时刻；若无解，输出 $-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$。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。