Minimum Cost Flow with Booster

This is a problem inspired by CCC2017 Senior T4 "Minimum Cost Flow". In Watermoo there are N buildings numbered 1,2,…,N and M pipelines connecting pairs of buildings. Building 1 is the only sewage treatment plant. Each pipeline has a maintenance cost and can be either active or inactive. A set of active pipelines forms a valid scheme if building 1 is connected (directly or indirectly) to every other building.

The city government currently uses a valid scheme consisting of exactly N-1 pipelines (i.e. a spanning tree), but it turns out that this scheme is very expensive because the total cost is simply the sum of the maintenance fees of the active pipelines.

Fortunately, researchers have developed an imperfect pipeline booster. You can use the booster on one pipeline, reducing its maintenance cost from C to \(\max(0, C-D)\), where D is the booster strength. The final cost of a valid scheme is computed as the sum of the maintenance fees for all active pipelines with the booster applied on exactly one pipeline. In other words, if the active set (spanning tree) is \(T\), its cost is:

[ \text{Cost}(T)= \sum_{e\in T} C_e - \max_{e\in T} \min(C_e,D) ]

Your task is to reconfigure the network. Every day, you are permitted to activate one pipeline (which was inactive) and deactivate one pipeline (which was active). The final configuration must be a valid scheme (i.e. a spanning tree) whose total cost (using the booster on one pipeline optimally) is minimized among all valid schemes. Note that during the reconfiguration process the scheme might be temporarily invalid, but the final scheme must be valid.

Determine the minimum number of days (i.e. edge swap operations) required to reach an optimal configuration from the current configuration.

inputFormat

The first line contains three integers N, M and D (2 ≤ N, and M ≥ N-1), where N is the number of buildings, M is the number of pipelines, and D is the booster strength.

The following M lines each contain three integers u, v, C (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ C) describing a pipeline connecting buildings u and v with maintenance cost C. The first N-1 pipelines (lines) form the current valid scheme (spanning tree).

outputFormat

Output a single integer representing the minimum number of days (swap operations) required to transform the current configuration into an optimal valid configuration with the minimum total cost (after applying the booster optimally).

sample

3 3 500
1 2 1000
2 3 1
1 3 600

1