题目描述

小灰灰在河边捡到了一只青蛙，小蓝嫌弃它太胖，于是给它安排了如下锻炼。

小灰灰设置一张 $n$ 个结点 $m$ 条边的有向图，其中第 $i$ 个点编号为 $i$，第 $i$ 条边从结点 $u_i$ 指向结点 $v_i$，这条边的长度为 $len_i$。

小蓝把青蛙放在了结点 $1$，当青蛙跳到其指定的结点时就结束了锻炼。

青蛙具有一个初始跳跃能力 $k$ 和健康状态 $d = 1$，它每完成一次跳跃能够使得自己的跳跃能力提升 $d$ 点，然后使自己的健康状态提升 $1$ 点（也就是第 $i$ 次跳跃时能力增加 $i$ 点）。

请注意青蛙只能从一个结点跳跃到相邻的另一个结点，且需要满足链接这两个结点的边长度不超过青蛙当前的跳跃能力。

小灰灰捡的青蛙很聪明，但很懒。所以它会选择一个总跳跃次数最少的路径从点 $1$ 到终点。由于终点并不确定，现在，请你求解从结点 $1$ 到每个结点的最少跳跃次数。

特别地，对于某个结点如果不存在任何成功跳跃路径，输出 $-1$。

输入格式

第一行输入三个整数 $n, m, k$。

接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i, v_i, len_i$。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示从 $1$ 开始跳跃到结点 $i$ 所需要的最少跳跃次数。若无法到达则输出 $-1$。

样例1

8 11 2
1 2 5
1 5 2
5 2 4
5 3 1
3 4 5
4 6 8
6 5 1
2 7 8
3 1 4
6 7 15
8 1 1

0 4 2 3 1 4 5 -1

样例 1 解释

初始时，青蛙在点 $1$，跳跃能力为 $2$。

按该方式跳跃 $1$ 步即可到达点 $5$：$\texttt{1 5}$。

按该方式跳跃 $2$ 步即可到达点 $3$：$\texttt{1 5 3}$。

按该方式跳跃 $3$ 步即可到达点 $4$：$\texttt{1 5 3 4}$。

按该方式跳跃 $2$ 步即可到达点 $2$：$\texttt{1 5 3 1 2}$。

按该方式跳跃 $4$ 步即可到达点 $6$：$\texttt{1 5 3 4 6}$。

按该方式跳跃 $5$ 步即可到达点 $7$：$\texttt{1 5 3 1 2 7}$。

样例2

见选手目录下 $\texttt{jump/jump2.in}$ 和 $\texttt{jump/jump2.ans}$，该测试用例满足测试点 $1 \sim 3$ 的约束条件。

样例3

见选手目录下 $\texttt{jump/jump3.in}$ 和 $\texttt{jump/jump3.ans}$，该测试用例满足测试点 $4 \sim 6$ 的约束条件。

样例4

见选手目录下 $\texttt{jump/jump4.in}$ 和 $\texttt{jump/jump4.ans}$，该测试用例满足测试点 $13 \sim 18$ 的约束条件。

数据范围

对于 $100\%$ 的数据：

保证：

• $1 \le n \le 10^5$
• $1 \le m \le 2 \times 10^5$
• $1 \le u_i, v_i \le n$
• $1 \le len_i, k \le 10^5$
• 图上没有重边和自环

各测试点的附加限制如下表所示：

特殊性质 A：$u_i< v_i$。

特殊性质 B：$len_i = 1$。

特殊性质 C：$n\le 10^4$ 且 $len_i,k_i\le 100$ 。

点击下载大样例