题目描述

译自 CCC2017 Senior T4. Minimum Cost Flow

Watermoo 中有编号为 $1,2,\dots,N$ 的建筑物。其中还有 $M$ 条管道将建筑物两两连接。由于城市规划的疏漏，$1$ 号建筑是全市唯一的污水处理厂。每条管道可能是活动的或是非活动的。如果建筑 $1$ 通过活动管道直接或是间接地与其他每个建筑连通，则称活动管道集是一个有效的方案。（每条管道将两个建筑直接连接。如果建筑 $X$ 直接或间接连接建筑 $Y$，且建筑 $Y$ 直接或间接连接建筑 $Z$，那么我们说 $X$ 和 $Z$ 间接连接。）

Watermoo 的市政府正在使用一个 $N-1$ 条管道组成的显然有效的方案，但是这使得政府已经透支很多经费了！每条管道都有各自的月维修费，这是在其活动时必须支付的，一个有效方案的总成本为所有有效管道的维修费的总和。（非活动的管道不花费一分钱。）

此外，一个好消息是：Watermoo 大学的研究人员开发出了一种不完善的管道推进器，你可以在一条管道上使用它。它将从 $C$ 到 $\mathrm{max}(0,C-D)$ 降低该管道的维修成本，$D$ 为该推进器的强度。

市政府希望将成本降到最低，同时也希望你能尽快完成这个任务。每天，城市会允许你激活一条管道并关闭另一条管道。问：你需要多少天才能使一组活动管道形成一个有效方案并使其在所有有效方案和推进方案中费用最小？

请注意，在你规划的过程中方案可能会无效，但是到最后，他应该是一个有效的方案。

输入格式

第一行，三个整数 $N,M$ 和 $D(1 \le N \le 100\ 000,N - 1 \le M \le 200\ 000,0 \le D \le 10^9)$。

接下来 $M$ 行，每行三个整数 $A_i,B_i$ 和 $C_i$，表示有一条月维修成本为 $C_i$ 的管道从建筑 $A_i$ 连接到建筑 $B_i(1 \le A_i,B_i \le N,1 \le C_i \le 10^9)$。

前 $N-1$ 行表示 Watermoo 正在使用的有效方案。

保证数据没有重边和自环。

输出格式

输出一行，一个整数，表示完成任务的最小天数。如果初始方案即最优方案，输出0。

4 4 0
1 2 1
2 3 2
3 4 1
4 1 1

1

5 6 2
1 2 5
2 3 5
1 4 5
4 5 5
1 3 1
1 5 1

2

4 4 0
1 2 715827882
2 3 715827882
3 4 715827882
4 1 715827884

0

数据范围与提示

对于 $\frac3{15}$ 的数据，$N \le 8,M \le 28,D=0$。

对于另外 $\frac5{15}$ 的数据，$N \le 1\ 000,M \le 5\ 000,D=0$。

对于另外 $\frac3{15}$ 的数据，$D=0$。

对于另外 $\frac2{15}$ 的数据，$N \le 1\ 000,M \le 5\ 000$。