P13860 [SWERC 2020] Jogging

菲比听说运动对身心健康都有着极大影响。她以前从未慢跑过，现在想尝试一下。但她知道自己很容易感到无聊，难以重复做同一件事。为了养成慢跑习惯，菲比决定接受一项挑战：只要能找到有趣的路线，她就会每天晚上出去跑步。对她而言，若路线会经过一条她之前没跑过的街道，这条路线就是有趣的。菲比希望你帮忙分析，若规划得当，她最多能跑步多少天。 菲比会向你提供她所在社区的相关信息作为输入。她住在一个十字路口，同时会描述社区里所有的十字路口。她还会告知哪些十字路口之间有街道相连，以及每条街道的长度（以米为单位）。每条街道都连接两个不同的十字路口，且不存在两条不同的街道连接同一对十字路口的情况。此外，你可以默认菲比描述的所有街道都能从她家抵达，且由于菲比是步行，这些街道都可以双向通行。 一次有效的跑步需从菲比家出发并回到家，且跑步长度需在她指定的范围内。当菲比进入一条街道时，她无需跑完整条街道（可以在任意位置转身），但即便如此，在判断跑步是否 “有趣” 时，仍会将其视为已经见过了整条街道。若一次跑步包含了一条之前跑步中未出现过的街道（或街道的某一段），这次跑步就会被认定为 “有趣”。需要注意的是，抵达某个十字路口并不等同于访问了该路口相邻的所有街道。

输入以一行内容开头，包含四个用空格分隔的整数，顺序依次为 $I$、$S$、$L$、$U$。各参数含义如下： $I$ 表示社区内十字路口的数量。 $S$ 表示街道的数量。 $L$ 表示一次有效跑步的最小长度（单位：米）。 $U$ 表示一次有效跑步的最大长度（单位：米）。 随后是 $S$ 行内容，每行代表一条街道。每行包含三个用空格分隔的整数，顺序依次为 $i$、$j$、$ℓ$。各参数含义如下： 整数 $i$ 和 $j$ 是该街道连接的两个十字路口的编号。 $ℓ$ 是该街道的长度（单位：米）。 所有十字路口的编号范围为 $0$ 到 $I - 1$，其中菲比（Pheobe）居住在编号为 $0$ 的十字路口。

输出一行内容，包含一个整数，该整数表示 “有趣的跑步” 所能构成的最长序列的长度（即最多能跑步的天数）。

##### 示例解释 1 以下是针对第一个示例输入的一份为期 $3$ 天的 “有趣跑步” 计划： 第一天，在连接十字路口 $0$ 和 $1$ 的街道上来回跑步（总长度 $80$ 米）。 第二天，沿街道向十字路口 $2$ 的方向跑 $40$ 米，之后沿原路返回（总长度 $80$ 米）。 第三天，先沿街道跑到十字路口 $1$，再向十字路口 $2$ 的方向跑 $5$ 米，之后沿原路返回（总长度 $90$ 米）。 ##### 示例解释 2 以下是一个有效的跑步方案：从十字路口 $0$ 跑到十字路口 $1$，再返回十字路口 $0$，接着向十字路口 $1$ 的方向跑 $0.5$ 米，最后返回十字路口 $0$。 - $1 \le I \le 100\,000$ - $0 \le S \le 100\,000$ - $1 \le L \le U \le 42\,195$ (菲比不会跑超过一场马拉松的距离) - $1 \le \ell \le 1\,000$