4164 - 寻宝
小 A 开发的电子游戏《寻宝》，将游戏场景设置在了校园内。
在游戏中，校园内的 N 个地点（编号 1 到 N）之间修建了 M 条单向通道。第 i 条通道从地点 U_i 通往地点 V_i，并且这条通道上散落着 C_i 枚金币。
你从起点地点 1 出发，游戏开始时，你持有 0 枚金币。沿着通道移动时，每经过一条通道需要花费 1 个单位时间，同时可以获取该通道上所有的金币。即使你之前已经走过这条通道并获取过金币，下次再次经过时，金币依然会重新出现，你仍然可以再次获取。
地点 N 处设置了一个游戏“结算点”。当你到达地点 N 时，你可以选择立即结束游戏，也可以继续在游戏中校园内的地图上内移动，获取更多金币。
假设从出发到游戏结束，总共过去了 T 个单位时间，你需要向活动主办方支付 T \times P 枚金币作为参加游戏的费用。
如果此时你持有的金币不足 T \times P，则只需要支付你当前全部的金币，剩余金币为 0。支付参加游戏的费用后，剩下的金币数就是你的最终收益。
请你求出：是否存在有限的最大收益？如果存在，请输出这个最大收益，不存在请输出 -1。
第一行输入三个整数 N、M、P。
接下来 M 行，每行三个整数 U_i、V_i、C_i，表示一条从 U_i 到 V_i 的单向通道，通道上有 C_i 枚金币。
按题目要求输出一个整数。
输入
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
样例说明 1
从地点 1 到地点 3 有两种主要路径：
- 路径 1→2→3：共获取 20+30=50 枚金币，用时 2 分钟，需支付 20 枚金币，收益 50-20=30。
- 路径 1→3：获取 45 枚金币，用时 1 分钟，支付 10 枚金币，收益 45-10=35。
因此最大收益为 35。
样例说明 2
到达地点 2 后，可以在 2→2 的自环上无限次循环，每次获得 100 枚金币，收益可以无限大，因此输出 -1。
样例说明 3
唯一能到达地点 4 的路径用时 1 分钟，获取 1 枚金币，但需支付 10 枚时间税，收益 1-10 < 0，最终为 0。
虽然可以在地点 2 或 3 无限获取金币，但从这些地点无法到达地点 4，因此这些循环路径无效。
数据范围
对于 100\% 的数据，满足 2 \le N \le 2500，1 \le M \le 5000，1 \le U_i, V_i \le N，1 \le C_i \le 10^5，0 \le P \le 10^5，保证从地点 1 一定可以到达地点 N。