3200. [SYOI 2019] YH再聚

【题目背景】

  经过所有YH与YF的斗智斗勇，YF并没有成功阻止YH教更大范围的传播，也没有成功在庆典上完成他的屠杀行动，每一位在场的YH都开开心心地回了家，不仅共同在庆典享受欢乐时光，也结识了许多志同道合的YH。他们感受到了YH教深深的魔力，并在接下来的生活中，将YH精神放在心中，向更多人介绍YH教。

【题目描述】

  今年才是两周年庆典，以后的三周年，四周年，一百周年，888周年庆典，你都想参加，庆典官方并不希望同一个人去太多次，毕竟YH教发展速度过于快，人数增长飞快，庆典无法容纳那么多人。

  庆典官方即YH教元老给每一位YH一个极限值，表示你可以支配的全部路径费用。

  你的位置在 $1$，庆典位置在 $N$，中间有许多节点，同时也有许多路径连接节点，给定每条路径的花费，定义一次参加的费用为从 $1$ 到 $N$ 所经过的路径和。

  官方并不希望你每次都走相同的最短路径使参加次数最多，所以规定每一次的路径不能相同，即只要有一条边不同即可。

【输入格式】

  第一行三个数$ N，M，E $表示节点个数，路径个数，极限值。

  接下来 $M$ 行，每行三个数 $u,v,e,$表示从节点 $u$ 到节点 $v$ 存在一条路径，路径花费为 $e$。

【输出格式】

  一个整数，表示一共能参加多少次庆典。

  输入数据保证至少可以参加一次庆典。

【样例输入】

4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5

【样例输出】

3

【提示】

一共有4种路径：

1->4，花费 1.5

1->2->1->4，花费 4.5

1->3->4，花费 4.5

1->2->3->4，花费 4.5

显然最多只能完成其中的3条路径（选第一种方式，后三种方式仍选两个），即最多可以参加3次庆典。

如果将 E=14.9 改为 E=15，则可以完成以上全部路径，答案变为 4。

10% 数据满足：  N<=6 M<=15

20% 数据满足：  N<=100 M<=300 E<=100且E和所有的ei均为整数（可以直接作为整型数字读入）。

所有数据均满足：2 <= N <= 5000，1 <= M <= 200000，1<=E<=10^7，1<=ei<=E，E和所有的ei为实数。

【来源】

LGLJ