题目描述

有一个有向图，点的编号为 $1 \sim N$，有 $M$ 条边，每条边为 $a_i \to b_i$，这条边上有 $c_i$ 枚硬币，此外节点 $N$ 上还有个按钮。

您从节点 $1$ 开始移动，初始硬币为 $0$，你需要抵达 $N$，经过每条边耗时 $1$ 分钟，每次经过一条边你都能收获硬币，无论重复多少次。

当您抵达 $N$ 时，你可以结束游戏，也可以继续游戏，但是当你结束游戏的时候，你需要支付 $T \times P$ 枚硬币，当您的硬币少于这个值时，你需要支付全部的硬币。

你的分数就是在付款后所拥有的硬币数量，如果可以确定能获得一个最大分数，你需要输出可以获得的分数的最大值。

输入格式

第一行包含三个整数 $N, M, P$。

接下来 $M$ 行，每行三个整数 $a_i, b_i, c_i$，表示顶点 $a_i$ 到顶点 $b_i$ 存在一条有向边，这条边上有 $c_i$ 枚硬币。

$2 \le N \le 2500$，$1 \le M \le 5000$，$1 \le a_i, b_i \le N$，$1 \le c_i \le 10^5$，$0 \le P \le 10^5$。

输出格式

可以获得的分数的最大值。

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