Cave Trips (PY)

The management of the Highlands Lakes National Park is planning a new collection of short tourist trips in the Park. This time, the trips will visit only the caves in the area. The caves are connected by direct paths. Each direct path connects two caves and there is no other cave along any direct path. Also, any two caves are connected by at most one direct path. There are safety issues related to the caves sightseeing. Therefore, all trips are subject to the following limitations.
Each direct path in the trip must be traveled only once. A trip must visit exactly four different caves and it must start and end at the same cave. There must be no direct path between the visited caves other from those which are part of the trip. A trip cannot be too short and also it cannot be too long. The length limits are fixed they are the same for all possible trips. The length of a trip is the sum of the lengths of all direct paths in the trip.
It is obvious to the management that there should be more ways how to construct a trip.

     

Image 1. Examples of connections between the caves. The examples correspond to the data of Example 1, 2 and 3 below. In case a), there are 3 trips represented by the following 4-tuples of caves: (0, 1, 2, 3), (0, 1, 4, 5), (2, 3, 6, 7). In case b), there are 8 trips. Each trip is represented by a 4-tuple of caves which contains caves 0 and 6 and two more caves. The only 4-tuples which do not represent a trip are (0, 1, 2, 6) and (0, 4, 5, 6), those trips would be too short or too long. In case c), there are 2 trips represented by the 4-tuples of caves: (0, 1, 4, 5), (5, 6, 9, 10).

The task

You are given the scheme of direct paths connecting the caves in the Park. Also, you are given the length of each direct path and the upper and lower limit of a trip length. Count the number of possible trips.

Two trips are considered different if there is least one cave which is a part of one trip and not a part of the other trip. Otherwise, the trips are considered identical.

Input

The first input line contains four integers N, M, L1, L2 separated by space. The values indicate (in this order) the number of caves in the park, the number of direct path between the caves, minimum possible length of a trip and the maximum possible length of a trip. The caves are labeled by integers 0, 1, ..., N−1. Next, there are M text lines, each describe one pair of directly connected caves. Each line contains three integers A, B, C separated by space. A and B represent labels of two caves connected by a direct path, C is the length of the path. The order of cave labels on a line and the order of cave pairs in the input is arbitrary.
It holds, 4 ≤ N ≤ 103, 4 ≤ M ≤ 104. All lengths of direct connections between the caves are positive and less than 1000.

Output

The output contains one text line with one integer representing the number of different cave trips.

Example 1

Input
8 12 16 20
0 3 2
1 2 4
0 1 5
3 2 6
4 7 1
5 6 3
4 5 6
7 6 5
0 4 1
3 7 2
1 5 4
2 6 3
Output
3
The scheme presented in Example 1 is depicted in Image 1a).

Example 2

Input
7 10 17 27
0 1 1
0 2 2
0 3 3
0 4 4
0 5 5
1 6 6
2 6 7
3 6 8
4 6 9
5 6 10
Output
8
The scheme presented in Example 2 is depicted in Image 1b).

Example 3

Input
12 19 75 95
0 1 10
1 2 30
2 3 10
4 5 30
5 6 10
6 7 10
8 9 60
9 10 40
10 11 10
0 4 30
4 8 20
1 5 20
5 9 10
2 6 40
6 10 20
3 7 10
7 11 30
5 8 5
6 11 5
Output
2
The scheme presented in Example 3 is depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set