配点 : $500$ 点

問題文

$1$ から $N$ までの番号がつけられた $N$ 頂点と $M$ 辺からなる有向グラフがあります。 $i$ 番目の辺は頂点 $A_i$ から頂点 $B_i$ へと向かい、この辺の上には $C_i$ 枚のコインが置かれています。 また、頂点 $N$ にはボタンが設置されています。

このグラフ上でゲームを行います。 あなたは頂点 $1$ でコインを $0$ 枚持ってゲームを開始し、辺をたどってコインを拾いながら頂点 $N$ を目指します。 $1$ 本の辺を通るには $1$ 分の時間がかかり、辺を通るたびにその辺の上に置かれているすべてのコインを拾うことができます。 ゲームの世界ではよくあるように、ある辺を通ってその上のコインを拾っても、その辺を次に通る際には同じ枚数のコインが再び出現しており、それらを再び拾うことができます。

頂点 $N$ に到着したとき、ボタンを押してゲームを終了することができます。(ボタンを押さずに移動を続けることもできます。) ただし、ゲームを終了する際に、ゲーム開始からの経過時間を $T$ 分として $T \times P$ 枚のコインの支払いが要求されます。持っているコインの枚数が $T \times P$ 枚未満の場合は、代わりに持っているコインをすべて支払います。

この支払いの後に残ったコインの枚数があなたのスコアとなります。 獲得できるスコアの最大値が存在するか判定し、存在する場合はその最大値を求めてください。

制約

• $2 \leq N \leq 2500$
• $1 \leq M \leq 5000$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^5$
• $0 \leq P \leq 10^5$
• 入力中の値はすべて整数である。
• 頂点 $1$ から頂点 $N$ に到達することが可能である。

入力

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

$N$ $M$ $P$

$A_1$ $B_1$ $C_1$

$:$

$A_M$ $B_M$ $C_M$

出力

獲得できるスコアの最大値が存在する場合はその最大値を、存在しない場合は -1 を出力せよ。

3 3 10
1 2 20
2 3 30
1 3 45

35

頂点 $1$ から頂点 $3$ に移動する方法は以下の $2$ 通りです。

• 頂点 $1 \rightarrow 2 \rightarrow 3$: 道中でコインを $20 + 30 = 50$ 枚拾う。ゲーム開始から $2$ 分後に頂点 $3$ に着き、ボタンを押してコインを $2 \times 10 = 20$ 枚支払い、$50 - 20 = 30$ 枚残る。
• 頂点 $1 \rightarrow 3$: 道中でコインを $45$ 枚拾う。ゲーム開始から $1$ 分後に頂点 $3$ に着き、ボタンを押してコインを $1 \times 10 = 10$ 枚支払い、$45 - 10 = 35$ 枚残る。

よって、獲得できるスコアの最大値は $35$ です。

2 2 10
1 2 100
2 2 100

-1

頂点 $1$ から伸びる辺を通ると頂点 $2$ に着き、ここで頂点 $2$ から自分自身へと向かう辺を $t$ 回通ってからボタンを押すとスコアは $90 + 90t$ となります。よってスコアは無限に高めることができ、獲得できるスコアの最大値は存在しません。

4 5 10
1 2 1
1 4 1
3 4 1
2 2 100
3 3 100

0

頂点 $1$ から頂点 $4$ へと直接向かう辺を通ること以外に頂点 $1$ から頂点 $4$ に移動する方法はありません。この辺の上で $1$ 枚のコインを拾いますが、ゲーム終了時に $10$ 枚のコインの支払いを要求されてスコアは $0$ となります。

なお、頂点 $1$ から頂点 $2$ へと向かう辺を通るとその後コインを無限に拾えますが、頂点 $4$ に到達してゲームを終了することができなくなるため無意味です。