You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

旅行者，在广袤的大陆里自由探索吧。

Description

大陆上分布着 $n(1 \leq n \leq 6 \times 10^5)$ 座城市，有 $m(n - 1 \leq m \leq 6 \times 10^5)$ 条双向道路连接这些城市，通过道路需要消耗相应的体力，而旅行者每天只有 $k(1 \leq k \leq 5000)$ 点体力值。出生在边远小城 $1$ 的他想要前往圣城 $n$ , 请你告诉他最少需要几天。

Format

Input

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

接下来 $m$ 行，每行三个整数 $u, v, w$ 表示城市 $u$ 和城市 $v (1 \leq u, v \leq n)$ 之间有一条需要消耗 $w(1 \leq w \leq k)$ 点体力值的道路

Output

一个整数，表示最少需要几天到达圣城

Samples

1 0 1

1

9 12 3
1 2 1
1 4 1
2 3 1
2 5 2
3 6 1
4 5 2
4 7 1
5 6 2
5 8 2
6 9 1
7 8 1
8 9 1

2

Hint

(1)--1--(2)--1--(3)
 |       |       |
 1       2       1
 |       |       |
(4)--2--(5)--2--(6)
 |       |       |
 1       2       1
 |       |       |
(7)--1--(8)--1--(9)

一种可行的方案是，第一天消耗 $1$ 点体力走到 $2$ , 第二天开始时体力由 $2$ 恢复到 $3$ , 消耗 $3$ 点体力，经由 $3, 6$ 走到 $9$ .