该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

终于放暑假了！

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

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

对于所有数据满足 $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

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

样例输出1

1

样例解释1

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

样例输入2

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

样例输出2

4

样例解释2

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