Ex - Prevented to Carry Snowman REVENGE

2 secs 1024 MB
matcharate12's icon matcharate12

Story

👿

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

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

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

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

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

:

:

ふふふ…

問題

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

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

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

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

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

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

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

入力

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

NN MM WW
A1A_1 B1B_1 C1C_1
A2A_2 B2B_2 C2C_2
⋮\vdots
AMA_M BMB_M CMC_M

制約

  • 2≤N≤2×1042\le N\le 2\times 10^4
  • 0≤M≤min⁡(2×104,N(N−1)2)0\le M\le \min(2\times 10^4,\cfrac{N(N-1)}{2})
  • 1≤W≤10121\le W\le 10^{12}
  • 1≤Ai≠Bi≤N1\le A_i\ne B_i\le N
  • 1≤Ci≤10121\le C_i\le 10^{12}
  • i≠j⇒(Ai,Bi)≠(Aj,Bj)i\ne j\Rightarrow (A_i,B_i)\ne (A_j,B_j)
  • 街 11 からどのような移動をしたとしても、各街には 11 度しか訪れることができない

出力

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

入出力例

入力例1
5 6 30
1 2 10
2 3 20
2 5 30
2 4 10
3 4 10
5 4 20
出力例1
35

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

  • 街 11 から街 22 に行く。雪だるまの大きさは 30+10−20=2030+10-20=20 となる
  • 街 22 から街 55 に行く。雪だるまの大きさは 20+30−20=3020+30-20=30 となる

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

入力例2
2 1 1
1 2 100000
出力例2
100001
入力例3
10000 0 100000
出力例3
1

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

入力例4
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
出力例4
189

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

Submit


Go (1.21)