题目描述

There is a directed graph with $N$ vertices numbered $1$ to $N$ and $M$ edges. The $i$-th edge is directed from Vertex $A_i$ to Vertex $B_i$, and there are $C_i$ coins placed along that edge. Additionally, there is a button on Vertex $N$.

We will play a game on this graph. You start the game on Vertex $1$ with zero coins, and head for Vertex $N$ by traversing the edges while collecting coins. It takes one minute to traverse an edge, and you can collect the coins placed along the edge each time you traverse it. As usual in games, even if you traverse an edge once and collect the coins, the same number of coins will reappear next time you traverse that edge, which you can collect again.

When you reach Vertex $N$, you can end the game by pressing the button. (You can also choose to leave Vertex $N$ without pressing the button and continue traveling.) However, when you end the game, you will be asked to pay $T \times P$ coins, where $T$ is the number of minutes elapsed since the start of the game. If you have less than $T \times P$ coins, you will have to pay all of your coins instead.

Your score will be the number of coins you have after this payment. Determine if there exists a maximum value of the score that can be obtained. If the answer is yes, find that maximum value.

有一个有向图，图中有 $N$ 个顶点，编号为 $1$ 至 $N$ ，有 $M$ 条边。从顶点 $A_i$ 到顶点 $B_i$ 的 $i$ 条边上放置了 $C_i$ 枚硬币。此外，顶点 $N$ 上有一个按钮。

我们将在这个图上玩一个游戏。游戏开始时，顶点 $1$ 上的硬币数量为零，游戏开始后，我们一边收集硬币，一边穿越边，前往顶点 $N$ 。穿越一条边需要一分钟，每次穿越边时都可以收集沿边放置的硬币。与通常游戏一样，即使您穿越了一次边缘并收集了硬币，下次穿越该边缘时也会再次出现相同数量的硬币，您可以再次收集。

到达顶点 $N$ 后，按下按钮即可结束游戏。(您也可以选择离开顶点 $N$ 而不按下按钮继续游戏）。不过，当您结束游戏时，会被要求支付 $T \times P$ 枚金币，其中 $T$ 是游戏开始后已经过去的分钟数。如果您的金币少于 $T \times P$ ，您将不得不支付所有金币。

您的得分就是您支付后拥有的金币数量。确定是否存在可获得的最大得分值。如果答案是肯定的，请找出最大值。

输入格式

输入内容按以下格式标准输入：

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

输出格式

如果存在可获得的最大分值，则打印该最大值；否则，打印 -1。

样例 #1

样例输入 #1

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

样例输出 #1

35

样例 #2

样例输入 #2

2 2 10
1 2 100
2 2 100

样例输出 #2

-1

样例 #3

样例输入 #3

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

样例输出 #3

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$
• 所有输入值均为整数。
• 顶点 $N$ 可以从顶点 $1$ 到达。

样例 $1$ 解释

从顶点 $1$ 到顶点 $3$ 有两条路可走：

• 顶点 $1 \rightarrow 2 \rightarrow 3$ ：您可以在途中收集 $20 + 30 = 50$ 枚金币。游戏开始两分钟后，您按下按钮，支付了 $2 \times 10 = 20$ 个金币，还剩下 $50 - 20 = 30$ 个金币。
• 顶点 $1 \rightarrow 2$ ：您在途中收集了 $45$ 枚金币。游戏开始一分钟后，您按下按钮，支付了 $1 \times 10 = 10$ 枚金币，您还剩下 $45 - 10 = 35$ 枚金币。

因此，可以获得的最高分是 $35$ 。

样例 $2$ 解释

从顶点 $1$ 开始的边将带您到达顶点 $2$ 。如果您从顶点 $2$ 沿着边延伸到顶点 $t$ 并按下按钮，您的分数将是 $90 + 90t$ 。因此，您可以无限增加您的分数，这意味着您所能得到的分数没有最大值。

样例 $3$ 解释

从顶点 $1$ 到顶点 $4$ 除了直接穿过顶点 $1$ 到顶点 $4$ 的边之外，别无他法。您将在这条边上拾取一枚硬币，但在被要求支付 $10$ 枚硬币后，您的得分将是 $0$ 。

请注意，如果您穿过顶点 $1$ 到顶点 $2$ 的边缘，您可以收集到无限多的硬币，但这是没有意义的，因为您再也无法到达顶点 $4$ 并结束游戏。