| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 62 | 37 | 34 | 68.000% |
In the Waterland country, there are n lakes (numbered from 1 to n) and m channels between them. The width (in meters) of each channel is known. Navigation in the channels can be performed in both directions. It is known that a boat with width of one meter can reach any lake, starting from lake number 1.
Write program channels, which calculates the minimum number of channels that should be widened, so that a boat with width of k meters can make a trip between every two lakes (the boat can move from one lake to another, if its width is less than or equal to the width of the channel, connecting the lakes).
On the first line of the standard input are given integers, n and m (1 < n ≤ 1000, 1 < m ≤ 100000).
On each of the next m lines are given three integers, i, j and w, showing that there is a channel of width w (1 ≤ w ≤ 200) between lakes, i and j (1 ≤ i, j ≤ n).
On the last line is given the integer k (1 ≤ k ≤ 200).
On a line of the standard output the program have to write one integer: the minimum number of channels that should be widened.
6 9 1 6 1 1 2 2 1 4 3 2 3 3 2 5 2 3 4 4 3 6 2 4 5 5 5 6 4 4
2