2826: 调整

已给定一个 N个点 M条边的有向图，点编号为1到N，第i条边为 （ui，vi）， 权值为 wi。你可以进行一次操作，使得任意条边的权值变成非负整数。要求进行尽量少的操作次数，使得点 1到点 N的最短路径长度变成 c。

题目保证， c小于在未进行任何操作之前的原图中 1到 N的最短路长度。

第一行三个整数，第一行三个整数，N，M和 c

接下来 M行，每一条边的信息 ui，vi和 wi，第 i行的表述第 i条边的信息。 保证不会有自环存在，对于不同的 i和 j，（ui，vi）不同于 （uj，vj）。

输出文件 tweak.out 一行一个整数，要进行最少多少次操作才能使得最短路长度变为 c。

3 3 3
1 2 3
2 3 3
1 3 8

1