Problem Description

Translated from CCC2017 Senior T4 "Minimum Cost Flow"

In Watermoo, there are buildings numbered $1, 2, \dots, N$. There are also $M$ pipes connecting these buildings pairwise. Due to a flaw in city planning, building $1$ is the only sewage treatment plant in the city. Each pipe can be either active or inactive. A set of active pipes is considered a valid scheme if building $1$ is directly or indirectly connected to every other building through active pipes. (Each pipe directly connects two buildings. If building $X$ is directly or indirectly connected to building $Y$, and building $Y$ is directly or indirectly connected to building $Z$, then $X$ and $Z$ are indirectly connected.)

The city government of Watermoo is currently using a seemingly valid scheme consisting of $N-1$ pipes, but this has already drained the government's funds! Each pipe has its own monthly maintenance cost, which must be paid if the pipe is active. The total cost of a valid scheme is the sum of the maintenance costs of all active pipes. (Inactive pipes do not cost anything.)

Additionally, there is good news: researchers at Watermoo University have developed an imperfect pipe propulsion device that you can use on a pipe. It reduces the maintenance cost of that pipe from $C$ to $\max(0, C-D)$, where $D$ is the strength of the propulsion device.

The city government wants to minimize the cost and also wants you to complete the task as soon as possible. Each day, the city allows you to activate one pipe and deactivate another. The question is: how many days are needed to form a valid scheme with the minimum cost among all valid schemes and propulsion schemes?

Note that the scheme may become invalid during your planning process, but it should be valid by the end.

Input Format

The first line contains three integers $N, M$, and $D$ $(1 \le N \le 100,000, N-1 \le M \le 200,000, 0 \le D \le 10^9)$.

The next $M$ lines each contain three integers $A_i, B_i$, and $C_i$, indicating that there is a pipe with a monthly maintenance cost of $C_i$ connecting building $A_i$ to building $B_i$ $(1 \le A_i, B_i \le N, 1 \le C_i \le 10^9)$.

The first $N-1$ lines represent the valid scheme currently used by Watermoo.

It is guaranteed that there are no duplicate edges or self-loops in the data.

Output Format

Output a single integer, which is the minimum number of days required to complete the task. If the initial scheme is already the optimal one, output 0.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1

Sample Input #2

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

Sample Output #2

2

Sample Input #3

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

Sample Output #3

0

Notes/Hints

Explanation for Sample #1

Since $D=0$, the pipe propulsion device is useless.

On the first day, you should deactivate the pipe between building $2$ and $3$ and activate the pipe between building $4$ and $1$.

Explanation for Sample #2

A possible solution is: first install the propulsion device on the pipe connecting building $1$ and $2$, reducing its cost to $3$. On the first day, replace the pipe connecting $2$ and $3$ with the pipe connecting $1$ and $3$. On the second day, replace the pipe connecting $1$ and $4$ with the pipe connecting $1$ and $5$.

Additionally, installing the propulsion device on the pipes connecting $1$ and $3$ or $1$ and $5$ is pointless. Doing so would reduce the maintenance cost of those pipes to $0$, but the optimal cost is $10$ (as we have already found a scheme with a cost of $10$).

Explanation for Sample #3

The initial scheme is already the optimal one. Note the potential for integer overflow.

For $\frac{3}{15}$ of the data, $N \le 8, M \le 28, D=0$.

For another $\frac{5}{15}$ of the data, $N \le 1,000, M \le 5,000, D=0$.

For another $\frac{3}{15}$ of the data, $D=0$.

For another $\frac{2}{15}$ of the data, $N \le 1,000, M \le 5,000$.

见题面 Input 部分

见题面 Output 部分