你是一场程序设计竞赛的裁判。你正在为一道图论问题准备测试数据，该问题要求求解两点之间最小代价路径的代价。你生成了一些随机数据，但它们不够有趣。你希望制作一组测试数据，其答案为你期望的特定值（例如代表今年的数字 2010）。因此，你希望通过修改某些边的权值（代价），将从起点到终点的最小代价路径的代价微调（即“调整”）为给定的目标值。你应该使修改的边数尽可能少。

给定一个非负整数 $c$ 和一个有向图 $G$。图 $G$ 的每条边都关联一个非负整数代价。给定图 $G$ 中从一个节点到另一个节点的一条路径，我们可以将该路径的代价定义为构成该路径的所有边的代价之和。给定图 $G$ 中的一对节点，我们可以将它们之间的最小代价（即连接它们的所有路径中代价的最小值）作为它们之间的非负代价。

给定一个图和其中的一对节点，你需要调整边的代价，使得从一个节点到另一个节点的最小代价路径的代价等于给定的目标代价 $c$。你可以假设 $c$ 小于原图中给定两点之间的最小代价路径的代价。

例如，在图 G.1 中，给定图中从节点 1 到节点 3 的最小代价路径的代价为 6。为了将该最小代价路径的代价调整为 2，我们可以将从节点 1 到节点 3 的边的代价修改为 2。修改后，这条直连边就成为了最小代价路径。

再如，在图 G.2 中，给定图中从节点 1 到节点 12 的最小代价路径的代价为 4022。为了将该最小代价路径的代价调整为 2010，我们可以修改从节点 6 到节点 12 的边的代价，以及右半部分六条边中的任意一条。修改边的方法有很多种，但最少需要修改的边数为 2。

图 G.1：图的示例 1

图 G.2：图的示例 2

输入格式

输入由多个数据集（测试点）组成。每个数据集的格式如下：

$$ \begin{array}{lll} n & m & c \\ f_1 & t_1 & c_1 \\ f_2 & t_2 & c_2 \\ \vdots & & \\ f_m & t_m & c_m \end{array} $$

整数 $n$、$m$ 和 $c$ 分别表示节点数、边数和目标代价，它们之间用单个空格分隔，其中 $2 \le n \le 100$，$1 \le m \le 1000$ 且 $0 \le c \le 100000$。

图中的每个节点用 $1$ 到 $n$ 之间的整数表示。

接下来的 $m$ 行表示边：整数 $f_i$、$t_i$ 和 $c_i$（$1 \le i \le m$）分别表示第 $i$ 条边的起点、终点和关联的代价，它们之间用单个空格分隔。它们满足 $1 \le f_i, t_i \le n$ 且 $0 \le c_i \le 10000$。你可以假设当 $i \ne j$ 时，$f_i \ne t_i$ 且 $(f_i, t_i) \ne (f_j, t_j)$。

你可以假设，对于每个数据集，从节点 1 到节点 $n$ 至少存在一条路径，且给定图中从节点 1 到节点 $n$ 的最小代价路径的代价大于 $c$。

输入结束的标志是包含三个由单个空格分隔的零的一行。

输出格式

对于每个数据集，输出一行，包含为了使从节点 1 到节点 $n$ 的最小代价路径的代价等于目标代价 $c$ 而必须修改代价的最少边数。边的代价不能修改为负数。输出中不应包含任何其他多余字符。

样例

输入样例 1

3 3 3
1 2 3
2 3 3
1 3 8
12 12 2010
1 2 0
2 3 3000
3 4 0
4 5 3000
5 6 3000
6 12 2010
2 7 100
7 8 200
8 9 300
9 10 400
10 11 500
11 6 512
10 18 1
1 2 9
1 3 2
1 4 6
2 5 0
2 6 10
2 7 2
3 5 10
3 6 3
3 7 10
4 7 6
5 8 10
6 8 2
6 9 11
7 9 3
8 9 9
8 10 8
9 10 1
8 2 1
0 0 0

输出样例 1

1
2
3