Story

👿

今年もおつかれさまでした会をしようとしてる人たちに、またもやsummerrate君は意地悪をしようと思っているようです。

「まだ雪だるまを作ってる奴がいるな…じゃあもっともっともーっと壊してやる！！！！」

summerrate君は黒魔術を使い、街の個数分のクローンを作り、各街にばら撒きました。

ただ、おつかれさまでした会を開こうとしてる人たちも、そんなバカじゃありません。

冬が大好きな皆さんは雪が嫌いじゃないと思われますが、一旦ここはsummerrate君の味方になり、冬が好きな人が大切に作った雪玉を、””壊して””あげましょう。

:

:

ふふふ…

問題

matcha国にはまた雪が降っています。今度はgreentea君が雪だるまを作る番になったようです。

greentea君が通る街は $N$ 個あり、街と街を相互につなぐ道が $M$ 本あります。
それぞれ街には $1,2,\dots ,N$ と番号づけられており、$i\ (1\le i\le M)$ 本目の道は街 $A_i$ と街 $B_i$ をつないでいますが、街 $A_i$ は街 $B_i$ よりも標高が高いところにあります。また $i$ 本目の道の長さは $C_i$ であることがわかっています。

今、greentea君は重さ $W$ の雪だるまを持ちながら街 $1$ にいます。この雪だるまは $i$ 本目の道を通るたびに重さが $C_i$ ずつ増えていきます。
またgreentea君は上り坂が嫌いなので、坂道を下りながら街 $N$ に向かいたいと思っています。

しかし、雪が嫌いなrate君はこのgreentea君が持っている雪だるまを壊そうと思っています。
具体的には街 $1$ を除くすべての街に対してrate君を配置し、その街にgreentea君が訪れるたびにrate君は雪だるまの重さを $K$ だけ減少させることができます。どんどん減少させていき、最終的に雪だるまの重さが $0$ 以下になった瞬間、雪だるまは溶けて無くなります。

このとき、$K$ は正整数の範囲で決めることができ、決めた後にこの値を変更することはできません。

greentea君が雪だるまを転がしながらどのように移動したとしても雪だるまを街 $N$ に渡らせないようにするためには、$K$ を少なくともいくつに決めることが適切か求めてください。
ただし $K$ をどんな値に決めようとその目標を達成できない場合は、その旨を報告してください。

ただし、街 $1$ からどのような移動をしたとしても各街には $1$ 度しか訪れることができないことが保証されます。

入力

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

制約

• $2\le N\le 2\times 10^4$
• $0\le M\le \min(2\times 10^4,\cfrac{N(N-1)}{2})$
• $1\le W\le 10^{12}$
• $1\le A_i\ne B_i\le N$
• $1\le C_i\le 10^{12}$
• $i\ne j\Rightarrow (A_i,B_i)\ne (A_j,B_j)$
• 街 $1$ からどのような移動をしたとしても、各街には $1$ 度しか訪れることができない

出力

greentea君が雪だるまを転がしながら雪だるまを街 $N$ に渡らせないようにするための $K$ の最小値を出力せよ。
ただし $K$ をどのような値になろうとその目標を達成できないなら -1 を出力せよ。

入出力例

5 6 30
1 2 10
2 3 20
2 5 30
2 4 10
3 4 10
5 4 20

35

例えば $K=20$ とすると、次のように道をたどることで到達可能になってしまいます。

• 街 $1$ から街 $2$ に行く。雪だるまの大きさは $30+10-20=20$ となる
• 街 $2$ から街 $5$ に行く。雪だるまの大きさは $20+30-20=30$ となる

$K=35$ にすることで、街 $5$ にたどりつくときに雪だるまの大きさは $0$ 以下になります。
$K=34$ 以下では雪だるまの大きさを $0$ 以下にすることはできない移動方法が存在してしまいます。

2 1 1
1 2 100000

100001

10000 0 100000

1

そもそも道が一つも存在しないこともあります。
このとき街 $1$ から街 $10000$ にたどりつくことはできません。よって $K$ はどんな正整数でもよいので $K=1$ が最小です。

19 19 1225
1 2 72
3 2 97
2 4 112
2 5 112
5 6 121
6 7 77
7 8 101
8 9 114
9 10 114
10 11 121
11 12 67
12 14 104
11 13 114
13 14 105
14 15 115
15 16 116
16 17 109
17 18 97
18 19 115

189

$\bm{Happy\ Merry\ Christmas...}$🌟🎄