Jogging

Pheobe has heard that exercise has a tremendous effect on both physical and mental health. She has never gone jogging before, and she wants to try it. However, she gets bored quickly and finds it hard to repeat the same thing. To build a jogging habit, Pheobe takes on a challenge: she will go out for a run every evening as long as she can find an interesting path. A path is interesting if it goes through a street she has not run on before. Help Pheobe find the maximum number of days she can run if she plans well.

Pheobe gives you a description of her neighborhood. She lives at an intersection, and she describes all intersections in the neighborhood. She also tells you which intersections are connected by streets and the length of each street in meters. Every street connects two different intersections, and no two different streets connect the same pair of intersections. You may assume that Pheobe only describes streets reachable from her home, and that streets can be traversed in both directions because Pheobe travels on foot.

A valid run starts and ends at Pheobe's home, and its length must be within the range she specifies. When Pheobe enters a street, she does not have to go through the entire street. She can turn around at any point, but even then, the street counts as fully seen for the purpose of determining whether runs are interesting. A run is interesting if it includes a street (or a segment of one) that did not appear on any previous run. Reaching an intersection does not count as visiting all streets adjacent to it.

The first line contains four space-separated integers $I$ $S$ $L$ $U$. $I$ is the number of intersections, and $S$ is the number of streets. $L$ is the minimum length in meters of a valid run, and $U$ is the maximum length in meters of a valid run.

Each of the next $S$ lines describes a street with three space-separated integers $i$ $j$ $\ell$. Streets $i$ and $j$ are the intersections the street connects, and $\ell$ is the length of the street in meters. Intersections are numbered from $0$ to $I-1$, and Pheobe lives at intersection $0$.

Print a single line containing one integer: the length of the longest sequence of interesting runs.

• $1 \le I \le 100\,000$
• $0 \le S \le 100\,000$
• $1 \le L \le U \le 42\,195$ (Pheobe will not run more than a marathon)
• $1 \le \ell \le 1\,000$