AT_abc137_e [ABC137E] Coins Respawn

有一个由 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条边组成的有向图。第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$，这条边上放有 $C_i$ 枚硬币。此外，顶点 $N$ 上安装有一个按钮。 你将在这张图上进行游戏。你从顶点 $1$ 出发，初始时持有 $0$ 枚硬币，沿着边移动并拾取硬币，目标是到达顶点 $N$。每经过一条边需要 $1$ 分钟，并且每次经过一条边时都可以拾取该边上所有的硬币。和游戏世界常见设定一样，即使你已经经过某条边并拾取了硬币，下次再经过时该边上的硬币会再次出现，你仍然可以再次拾取。 到达顶点 $N$ 时，你可以按下按钮结束游戏（也可以选择不按按钮继续移动）。不过，结束游戏时，假设从游戏开始已经过去了 $T$ 分钟，你需要支付 $T \times P$ 枚硬币。如果你持有的硬币不足 $T \times P$，则需要支付你持有的全部硬币。 支付后剩下的硬币数就是你的得分。请判断是否存在可以获得的最大得分，如果存在则输出最大得分，否则输出 $-1$。

输入以如下格式从标准输入读入。 > $N$ $M$ $P$ > $A_1$ $B_1$ $C_1$ > $\vdots$ > $A_M$ $B_M$ $C_M$

如果存在可以获得的最大得分，则输出该最大值；如果不存在，则输出 $-1$。

## 限制条件 - $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$。 ## 样例解释 1  从顶点 $1$ 到顶点 $3$ 有以下两种方式： - $1 \rightarrow 2 \rightarrow 3$：途中共拾取 $20 + 30 = 50$ 枚硬币。到达顶点 $3$ 时已过去 $2$ 分钟，支付 $2 \times 10 = 20$ 枚硬币，剩下 $50 - 20 = 30$ 枚。 - $1 \rightarrow 3$：途中拾取 $45$ 枚硬币。到达顶点 $3$ 时已过去 $1$ 分钟，支付 $1 \times 10 = 10$ 枚硬币，剩下 $45 - 10 = 35$ 枚。 因此，最大得分为 $35$。 ## 样例解释 2  从顶点 $1$ 出发经过一条边到达顶点 $2$，然后可以在顶点 $2$ 上自环多次，每次都能拾取 $90$ 枚硬币。这样，最终得分为 $90 + 90t$，可以无限增加。因此不存在最大得分。 ## 样例解释 3  从顶点 $1$ 到顶点 $4$ 只有一条直接的边。经过这条边可以拾取 $1$ 枚硬币，但结束时需要支付 $10$ 枚硬币，因此得分为 $0$。 注意，虽然可以从顶点 $1$ 到顶点 $2$ 并在 $2$ 上无限拾取硬币，但无法到达顶点 $4$ 并结束游戏，因此没有意义。 由 ChatGPT 4.1 翻译