PIPI国有N座城市，编号1~N。城市间有M条双向的高速公路相连。每条公路都有一个车辆的最大总重限制，总重超过限制的车辆不能在该条公路上行驶。
现在PIPI希望将一批物资从1号城市运送到N号城市，货车总重是W。每经过一条公路需要缴纳1元的过路费，请你计算PIPI最少需要缴纳多少费用。
第一行包含3个整数N、M和W。
以下M行每行包含3和整数A、B和L。表示这条公路连接A号城市和B号城市，重量限制是L。
1 ≤ N ≤ 1000 1 ≤ M ≤ 500000 1 ≤ L, W ≤ 10000
3 3 86
1 2 100
2 3 100
1 3 50
2