题目描述

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

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

样例解释 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 翻译