Minimum Spanning Tree

Problem Source

BZOJ 2561

Problem Description

Given a connected undirected graph $G = (V, E)$ with positive edge weights, where $n = |V|, m = |E|$ and the $n$ vertices are numbered $1$ through $n$.

Given three positive integers $u, v, L\ (u \neq v)$. Suppose we now add an edge $(u, v)$ of weight $L$. What is the minimum number of edges we must delete so that this new edge could appear both in a minimum spanning tree and in a maximum spanning tree of the resulting graph?

Input Format

The first line contains two numbers $n, m\ (1 \le n \le 20000, 0 \le m \le 200000)$.

Each of the next $m$ lines contains three positive integers $x, y, w\ (x \neq y, 1 \le w \le 20000)$, indicating an edge $(x, y)$ of weight $w$ in $G$.

The last line contains three space-separated integers $u, v, L\ (u \neq v, 1 \le L \le 20000)$.

Output Format

Output one integer: the minimum number of edges that must be deleted.

Sample Input

3 2
3 2 1
1 2 3
1 2 2

Sample Output

1