题目描述

终于放暑假了！

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

他一共打算去 $n$ 个景点，他已经做好了景点之间的规划，一共有 $m$ 条道路。

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

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

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

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

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

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

输入格式

本题采用文件读写。

• 读入文件名：travel.in
• 写出文件名：travel.out

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

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

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

输出格式

输出一个整数，表示徐老师最少的调整次数。

样例

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

1

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

4

样例说明

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

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

数据范围与提示

• 对于所有数据，$2\le n\le 2\times 10^5$，$n-1\le m\le \min(2\times 10^5,\frac{n(n-1)}2)$，$1\le u_i,v_i\le n$，$1\le cost_i,P\le 10^9$。

• 保证 $u_i\ne v_i$。