E - 硬币的刷新

得分：500 点

问题描述

有一个有 $N$ 个顶点，编号从 $1$ 到 $N$，有 $M$ 条边的有向图。 第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$，这条边上有 $C_i$ 枚硬币。 此外，顶点 $N$ 上有一个按钮。

我们在这个图上玩一个游戏。 你从顶点 $1$ 开始，身上没有硬币，通过遍历边来前往顶点 $N$ 并收集硬币。 通过一条边需要花费一分钟，每次通过一条边都可以收集到其上的硬币。 如同游戏中的一般规则，即使你通过一条边并收集到硬币，下次经过该边时会重新出现同样数量的硬币，你可以再次收集。

当你到达顶点 $N$，你可以按下按钮结束游戏（你也可以选择不按下按钮离开顶点 $N$ 继续旅行）。 然而，当你结束游戏时，你需要支付 $T \times P$ 枚硬币，其中 $T$ 是游戏开始后经过的分钟数。如果你的硬币数少于 $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$ 有两条路径：

• 从顶点 $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 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$。你将在这条边上拾取一枚硬币，但在支付 $10$ 枚硬币后，你的得分将变为 $0$。

请注意，如果你遍历从顶点 $1$ 到顶点 $2$ 的边，你可以无限收集到硬币，但这是毫无意义的，因为你无法到达顶点 $4$ 并结束游戏。