当前没有测试数据。

题目描述

终于放暑假了！

Sam 决定出去旅游，但是在出门旅游前他需要规划好所有的旅游路线。

他一共打算去 $n$ 个景点，他已经做好了景点之间的规划，一共有 $m$ 条道路连接这些景点，保证任意两个景点之间互相可以到达。

对于旅游来说，路上的风景往往也非常有意义，所以 Sam 打算规划一下在道路之间花费的时间。

现在 Sam 已经做了一个初步的规划，对于第 $i$ 条道路来说，它连通的是 $u_i,v_i$ 两个景点，Sam 初步打算在这条路上花费 $cost_i$ 的时间。

现在 Sam 需要对道路规划进行进一步的优化：

1. 只保留 $n-1$ 条道路，只要保证通过这些道路，能确保 Sam 能通过这些道路到达任意城市即可。（因为 Sam 的目的是为了景点，在去过的景点之间频繁的来回穿梭并没有意义）。
2. Sam 可以调整保留下来的道路上花费的时间，但是每次调整只能选择一条道路，然后给它的 $cost_i +1$ 或者 $-1$ 。

最终 Sam 希望保留下来的道路中最大的花费时间 恰好 为 $P$。

现在 Sam 想知道，他最少需要调整几次？

输入格式

输入第一行包含两个整数 $n,m$，表示景点数量和道路数量。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,cost_i$ 表示一条道路的信息。

最后一行包含一个整数 $P$ 含义如题。

输出格式

输出一个整数表示 Sam 最少的调整次数。

输入输出样例 #1

输入 #1

4 5
1 2 10
1 3 5
2 3 8
2 4 8
3 4 6
7

输出 #1

1

输入输出样例 #2

输入 #2

4 5
4 1 10
1 2 8
2 3 8
2 4 1
3 4 9
6

输出 #2

4

说明/提示

数据范围

对于所有数据满足：

$2\leq n \leq 2\times 10^5, n-1 \leq m \leq \min(2\times 10^5, \frac{n(n-1)}{2}), 1 \leq u_i, v_i \leq n, 1 \leq cost_i,P \leq 10^9$。

且保证 $u_i \not= v_i$。

样例解释1

其中一种方案为：保留第 $2,3,5$ 三条道路，并且调整第 $3$ 条道路 $cost_i-1=7$。

样例解释2

其中一种方案为：保留第 $2,3,4$ 三条道路，并且将第 $2,3$ 条道路各调整 $2$ 次使得 $cost_i-2=6$，一共需要调整 $4$ 次。