408291: GYM103081 D Jogging

Pheobe has heard that exercise has a tremendous affect on both physical and mental health. She never went jogging before, and she wants to try it out. However, she knows that she gets bored quickly and it is difficult for her to repeatedly do the same thing. In order to get into the habit of jogging, Pheobe decided to take up a challenge: she will go out for a run every evening as long as she finds an interesting path to take. For her, a path is interesting if it goes through a street where she did not run before. Pheobe asks for your help in understanding what is the maximum number of days she can run if she plans well.

Pheobe gives you as input a description of her neighborhood. She lives on an intersection, and she describes all of the intersections in the neighborhood. She also tells you which intersections are connected by streets, and what is the length of each street in meters. Every street connects two different intersections, and it is not possible that two different streets connect the same two intersections. In addition, you may assume that Pheobe only describes streets that can be reached from her home and that streets can be traversed in both directions as Phoebe is on foot.

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

The input begins with one line containing four space-separated integers, $$$I$$$ $$$S$$$ $$$L$$$ $$$U$$$, in that order. $$$I$$$ represents the number of intersections in the neighborhood, and $$$S$$$ represents the number of streets. $$$L$$$ is the minimum number of meters in a valid run, and $$$U$$$ is the maximum number of meters in a valid run.

Then, follow $$$S$$$ lines, each line representing a street. Each such line contains $$$3$$$ space-separated integers, $$$i$$$ $$$j$$$ $$$\ell$$$, in that order. Integers $$$i$$$ and $$$j$$$ are the intersections that the street connects, and $$$\ell$$$ is the length of the street in meters. The intersections are numbered between $$$0$$$ and $$$I-1$$$ such that Pheobe lives in intersection number $$$0$$$.

Limits

• $$$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$$$

A single line containing a single integer holding the length of the longest sequence of interesting runs.

4 4 80 90
0 1 40
0 2 50
1 2 30
2 3 10

3

2 1 7 7
0 1 3

1

Sample Explanation 1

Here is an example for an interesting 3-day jogging plan for the first sample input:

• On the first day, run back and forth on the street between $$$0$$$ and $$$1$$$ ($$$80$$$ meters).
• On the second day, run for 40 meters on the street to $$$2$$$ and then go back the same way ($$$80$$$ meters).
• On the third day, run on the street to $$$1$$$, then run for $$$5$$$ meters in the direction of $$$2$$$, and then go back the same way ($$$90$$$ meters).

Sample Explanation 2

Here is one possible valid run: Run from $$$0$$$ to $$$1$$$, then back to $$$0$$$, then half a meter in the direction of $$$1$$$, and then back to $$$0$$$.