Widening of Channels

Time limit1sMemory limit128 MB

Summary

Given a weighted undirected graph, find the minimum number of edges to widen to width k so that every pair of vertices is connected.

Level: Medium6 of 10
Topics: Graph, Union-find, Greedy, Sorting
Solved: No attempts yet

Problem

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

Input

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$ ).

Output

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

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3 3
1 2 5
2 3 5
1 3 5
5
```
Expected output
```
0
```
Example 3
Input
```
4 3
1 2 1
2 3 1
3 4 1
2
```
Expected output
```
3
```