题目描述
There are n cities in country X. Some pairs of cities are connected by bidirectional roads, and there exists one and only one path between every pair of cities.
Lily wants to take a trip in country X. She can start from any city, and she wouldn’t visit a city twice. Lily is effeminate, so the total distance of this trip should not be larger than L.
Your task is to calculate the number of all possible trips. Two trips are distinct if and only if the set of cities they contain are different.
输入
The first line contains two integers n and m, n is the number of cities, and m is the number of roads. The following m lines describe m roads, each of which contains three integers a, b, c, representing that a and b are connected by an undirected road which length is c. The last line contains a integer L.
1 < = n < = 100000, 1 < = c < = 10000, 1 < = L < = 1000000000.
输出
For each case, output a line contains a integer.
3 2
2 3 10
1 3 10
15
4 3
2 3 10
1 3 5
3 4 3
14