问题描述

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

示例输入 1

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

示例输出 1

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 2 10
1 2 100
2 2 100

示例输出 2

-1

从顶点 $1$ 沿着指向顶点 $2$ 的边遍历，然后再通过指向自身的边遍历 $t$ 次并按下按钮，你的分数将是 $90 + 90t$。因此，你的分数可以无限增加，这意味着不存在可以达到的最大分值。

示例输入 3

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

示例输出 3

0

除了直接遍历从顶点 $1$ 到顶点 $4$ 的边缘之外，没有其他方式可以从顶点 $1$ 到达顶点 $4$。你会在这条边上捡起一枚硬币，但在被要求支付 $10$ 枚硬币后，你的分数将是 $0$。

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