問題文

今、あなたは出町柳駅（地点 $1$）にいます。京大時計台前（地点 $N$）で行われる新歓イベントに参加したいです。

この地域には $N$ 個の地点と $M$ 本の双方向の道路があります。$i$ 番目の道路は地点 $u_i$ と地点 $v_i$ を結んでおり、この道路を通るには $t_i$ 分かかります。同じペアの地点を結ぶ道路が複数あったり、同じ地点同士を結ぶループのような道路があったりすることもあります。また、地点 $1$ からいくつかの道路を通ることでどの地点にも到達できます。

あなたは時刻 $0$ に地点 $1$ を出発して、道路で結ばれている地点への移動を繰り返します。同じ地点や道路を何度も通って時間調整をしても構いません。ただし、立ち止まるのはもったいないので、立ち止まることはしません。

新歓イベントは時刻 $0$ に最初に始まり、その後は $K$ 分ごとに繰り返し始まります。地点 $N$ にいるとき、あなたは新歓イベントの会場に入場することができます。地点 $N$ に到着しても、すぐには入場せず、再び移動を続けても構いません。

ただし、中途半端なタイミングで入場すると、すでに場が温まっていて少し気まずいです。そこで、気まずさを、

• あなたが実際に会場へ入場した時刻から見て、直前に開始したイベントから経過した時間(分)

で定義します。ちょうどイベント開始と同時に入場した場合、気まずさは $0$ です。

あなたは気まずさをなるべく小さくしたいです。気まずさとしてあり得る最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$
$u_1$ $v_1$ $t_1$
$\vdots$
$u_M$ $v_M$ $t_M$

• $2 \le N \le 2\times10^5$
• $1 \le M \le 2\times 10^5$
• $1 \le K \le 10^{18}$
• $1 \le u_i, v_i \le N$
• $1 \le t_i \le 10^{18}$
• 地点 $1$ からいくつかの道路を通ることで、どの地点にも到達できる
• 入力はすべて整数

出力

答えを $1$ 行に出力せよ。

サンプル

サンプル1

入力

3 3 10
1 2 3
2 3 4
1 3 15

出力

1

地点 $3$ では時刻 $0, 10, 20, \ldots$ に新歓イベントが開催されています。

地点 $1$ から地点 $3$ へ直接向かうと $15$ 分かかります。ここで入場することにすると、直前のイベントは時刻 $10$ に始まっているので、気まずさは $5$ となります。

一方で、$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$ と移動すると、$3+3+15=21$ 分かかります。ここで入場することにすると、直前のイベントは時刻 $20$ に始まっているので、気まずさは $1$ となります。

どのように移動しても気まずさ $0$ を達成できないので、気まずさの最小値は $1$ です。

2 3 4
1 1 4
1 1 8
1 2 999999999999999999

1

6 9 30
1 2 6
2 3 3
3 4 6
2 5 12
5 6 3
1 4 15
3 6 18
4 5 9
1 6 21

3

7 21 30
1 2 9
1 3 3
1 4 24
1 5 15
1 6 9
1 7 6
2 3 24
2 4 15
2 5 12
2 6 6
2 7 21
3 4 9
3 5 6
3 6 24
3 7 15
4 5 21
4 6 15
4 7 12
5 6 12
5 7 3
6 7 21

0