硬币游戏

题目描述

有一个由编号为 $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。

样例

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$ 结束游戏，因此没有意义。

数据范围

• $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$。