题目描述

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

我们在这个图上玩一个游戏。 你从顶点$1$开始，身上没有硬币，通过遍历边来前往顶点 $N$ 并收集硬币。 通过一条边需要花费一分钟，每次通过一条边都可以收集到其上的硬币。如同游戏中的一般规则，即使你通过一条边并收集到硬币，下次经过该边时会重新出现同样数量的硬币，你可以再次收集。当你到达顶点 $N$，你可以按下按钮结束游戏(你也可以选择不按下按钮离开顶点 $N$ 继续旅行)。 然而，当你结束游戏时，你需要支付 $T \times P$ 枚硬币，其中 $T$ 是游戏开始后经过的分钟数。如果你的硬币数少于$T \times P$枚，你将支付全部硬币。

你的得分将是在支付后剩余的硬币数。 确定是否存在可以获得的最大得分。如果答案是肯定的，则找出最大得分。

输入

输入第一行三个整数$N,M,P$

接下来一共$M$行，每行三个整数$A,B,C$,表示从$A$到$B$硬币数目为$C$.

输出

如果存在可以获得的最大得分，则输出那个最大值；否则输出 -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$