Minimum Cost Flow

The city of Watermoo has buildings numbered $1$ through $N$, and $M$ pipes that connect pairs of buildings. Because of an oversight in urban planning, building $1$ is the only sewage treatment plant in the city.

Each pipe is either active or inactive. The set of active pipes is a valid plan if building $1$ is connected, directly or indirectly, to every other building using active pipes. A pipe directly connects a pair of buildings. Buildings $X$ and $Z$ are indirectly connected if $X$ is directly or indirectly connected to $Y$ and $Y$ is directly or indirectly connected to $Z$.

The municipal government of Watermoo runs a valid plan of $N - 1$ pipes today, and it considers that plan too expensive. Each pipe has a monthly maintenance fee that the city pays while the pipe is active, and the total cost of a plan is the sum of the maintenance fees of its active pipes. An inactive pipe costs nothing.

Researchers at the University of Watermoo built an experimental pipe enhancer that you can use on one pipe of your choice. Using it reduces that pipe's cost from $C$ to $\max(0, C - D)$, where $D$ is the strength of the enhancer.

The city wants the cost of the plan to be minimum, and it wants the work done quickly. Each day you can activate one pipe and deactivate another pipe. How many days do you need so that the set of active pipes is a valid plan whose cost is minimum over all valid plans and all choices of the enhanced pipe?

The plan may be invalid while you work, but it has to be a valid plan at the end.

The first line contains the integers $N$, $M$, and $D$. ($1 \le N \le 100000$, $N - 1 \le M \le 200000$, $0 \le D \le 10^9$)

Each of the next $M$ lines contains three integers $A_i$, $B_i$, and $C_i$, which means that a pipe connects building $A_i$ and building $B_i$ and costs $C_i$ per month while it is active. ($1 \le A_i, B_i \le N$, $1 \le C_i \le 10^9$)

The first $N - 1$ of these lines are the valid plan the city is using now.

At most one pipe connects any two buildings, and no pipe connects a building to itself.

Print one integer on a single line, the minimum number of days needed to finish the task. If the plan the city is using now is already optimal, print $0$.

In the first example $D = 0$, so it does not matter which pipe you use the enhancer on, because no maintenance fee changes. On the first day, deactivate the pipe between building $2$ and building $3$ and activate the pipe between building $4$ and building $1$.

One way to finish the second example in the minimum number of days is this. First use the enhancer on the pipe between building $1$ and building $2$ to reduce its cost to $3$. On the first day, replace the pipe between building $2$ and building $3$ with the pipe between building $1$ and building $3$. On the second day, replace the pipe between building $1$ and building $4$ with the pipe between building $1$ and building $5$. The cost of the optimal plan is $10$. Using the enhancer on the pipe between building $1$ and building $3$, or on the pipe between building $1$ and building $5$, is not allowed in any solution: that pipe would have a maintenance fee of $0$, the optimal plan would then cost $11$, and a cost of $10$ is already reachable.

In the third example the plan the city is using now is already optimal. Watch out for integer overflow when you implement your solution.