P4806 [CCC 2017] Minimum Cost Flow

**Translated from [CCC 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Senior T4 “[Minimum Cost Flow](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%201/seniorEF.pdf)”.** In Watermoo, there are buildings numbered $1,2,\dots,N$. There are also $M$ pipes, each connecting a pair of buildings. Due to an oversight in city planning, Building $1$ is the only sewage treatment plant in the city. Each pipe can be *active* or *inactive*. If Building $1$ is directly or indirectly connected to every other building using only active pipes, then the set of active pipes is called a valid plan. (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 we say $X$ and $Z$ are indirectly connected.) The city government of Watermoo is currently using an obviously valid plan consisting of exactly $N-1$ pipes, but this has already pushed the budget too far. Each pipe has its own monthly maintenance cost, which must be paid if the pipe is active. The total cost of a valid plan is the sum of the maintenance costs of all active pipes. (Inactive pipes cost nothing.) There is also good news: researchers at Watermoo University have developed an imperfect pipe booster, which you may use on exactly one pipe. It reduces that pipe’s maintenance cost from $C$ to $\mathrm{max}(0,C-D)$, where $D$ is the strength of the booster. The government wants to minimize the cost, and also wants you to finish as quickly as possible. Each day, the city allows you to activate one pipe and deactivate one other pipe. How many days do you need so that the set of active pipes forms a valid plan and has the minimum possible cost among all valid plans and all choices of where to use the booster? Note that during your process, the plan may be invalid, but in the end it must be a valid plan.

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$, meaning there is a pipe with monthly maintenance cost $C_i$ connecting building $A_i$ and building $B_i$ $(1 \le A_i, B_i \le N, 1 \le C_i \le 10^9)$. The first $N-1$ of these $M$ lines describe the valid plan Watermoo is currently using. It is guaranteed that there are no multiple edges and no self-loops in the testdata.

Output one line containing an integer, the minimum number of days needed to finish the task. If the initial plan is already optimal, output `0`.

#### Sample Explanation 1 Since $D=0$, the pipe booster is useless. On the first day, you should deactivate the pipe between buildings $2$ and $3$ and activate the pipe between buildings $4$ and $1$. #### Sample Explanation 2 One feasible solution is: first install the booster on the pipe connecting buildings $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$. In addition, installing the booster on the pipe connecting $1$ and $3$ or the pipe connecting $1$ and $5$ is meaningless. Doing so would make that pipe’s maintenance cost $0$, and the optimal total cost would be $11$ (as you can see, we have already found a plan with total cost $10$). #### Sample Explanation 3 The initial plan is already optimal. Please note integer overflow. For $\frac3{15}$ of the testdata, $N \le 8, M \le 28, D=0$. For another $\frac5{15}$ of the testdata, $N \le 1\ 000, M \le 5\ 000, D=0$. For another $\frac3{15}$ of the testdata, $D=0$. For another $\frac2{15}$ of the testdata, $N \le 1\ 000, M \le 5\ 000$. Translated by ChatGPT 5