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

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

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

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