Widening of Channels

In the country of Waterland there are $n$ lakes, numbered from $1$ to $n$, and $m$ channels connecting them. Each channel has a known width (in meters), and every channel can be navigated in both directions. It is guaranteed that a boat one meter wide can reach every lake starting from lake $1$.

Write a program that computes the minimum number of channels that must be widened so that a boat $k$ meters wide can travel between every pair of lakes. A boat can pass through a channel only if its width is less than or equal to the width of the channel; that is, a channel of width $w$ can be used when $k \le w$. Widening a channel raises its width to at least $k$.

The first line contains two integers $n$ and $m$ ($1 < n \le 1000$, $1 < m \le 100000$).

Each of the next $m$ lines contains three integers $i$, $j$, and $w$, meaning that there is a channel of width $w$ between lakes $i$ and $j$ ($1 \le i, j \le n$, $1 \le w \le 200$).

The last line contains the integer $k$ ($1 \le k \le 200$).

Print a single integer: the minimum number of channels that must be widened.