题目描述

$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$ 枚未満の場合は、代わりに持っているコインをすべて支払います。

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

输入格式

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

$N$ $M$ $P$ $A_1$ $B_1$ $C_1$ $:$ $A_M$ $B_M$ $C_M$

输出格式

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

题目大意

有一个有向图，点的编号为 $1 \sim N$，有 $M$ 条边，每条边为 $a_i \to b_i$，这条边上有 $c_i$ 枚硬币，此外节点 $N$ 上还有个按钮。

您从节点 $1$ 开始移动，初始硬币为 $0$，你需要抵达 $N$，经过每条边耗时 $1$ 分钟，每次经过一条边你都能收获硬币，无论重复多少次。

当您抵达 $N$ 时，你可以结束游戏，也可以继续游戏，但是当你结束游戏的时候，你需要支付 $T \times P$ 枚硬币，当您的硬币少于这个值时，你需要支付全部的硬币。

你的分数就是在付款后所拥有的硬币数量，如果可以确定能获得一个最大分数，你需要输出可以获得的分数的最大值。

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

35

2 2 10
1 2 100
2 2 100

-1

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

0

提示

制約

• $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$ に到達することが可能である。

Sample Explanation 1

 頂点 $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$ です。

Sample Explanation 2

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

Sample Explanation 3

 頂点 $1$ から頂点 $4$ へと直接向かう辺を通ること以外に頂点 $1$ から頂点 $4$ に移動する方法はありません。この辺の上で $1$ 枚のコインを拾いますが、ゲーム終了時に $10$ 枚のコインの支払いを要求されてスコアは $0$ となります。 なお、頂点 $1$ から頂点 $2$ へと向かう辺を通るとその後コインを無限に拾えますが、頂点 $4$ に到達してゲームを終了することができなくなるため無意味です。