Edge Removal for Dual Spanning Tree Inclusion

Given a connected undirected graph G = (V, E) with positive edge weights. The graph has N vertices numbered from 1 to N and M edges. You are also given three positive integers: u, v (with u ≠ v) and L. Consider adding a new edge e₀ = (u, v) of weight L to G. Your task is to remove as few edges as possible from G such that in the resulting graph (after adding the new edge) there exist two spanning trees: one minimum spanning tree (MST) and one maximum spanning tree (MaxST) which both include the new edge e₀.

Explanation:

An edge can appear in some MST if it is not the unique heaviest edge in any cycle, and it can appear in some maximum spanning tree if it is not the unique lightest edge in any cycle. In our problem, after adding the new edge e₀ with weight L, in order for e₀ to possibly belong to an MST, every u–v path (not using e₀) must contain at least one edge of weight ≥ L. Similarly, for e₀ to be in some MaxST, every u–v path must contain at least one edge of weight ≤ L.

This observation leads to the following strategy: separate the edges of G into three categories based on weight relative to L:

• Edges with weight < L; call the subgraph formed by these edges Gₗₒw.
• Edges with weight = L; these are neutral and help satisfy both conditions.
• Edges with weight > L; call the subgraph formed by these edges Gₕᵢgh.

In order to guarantee that every u–v path contains at least one edge with weight ≥ L, we must remove enough edges from Gₗₒw so that u and v become disconnected in Gₗₒw. The minimum number of edges that need to be removed in Gₗₒw is exactly the minimum edge-cut (with each edge having capacity 1) between u and v in Gₗₒw.

Similarly, to ensure that every u–v path contains at least one edge with weight ≤ L, we must remove a minimum set of edges from Gₕᵢgh so that u and v are disconnected in Gₕᵢgh.

The final answer is the sum of these two minimum cuts:

minCut(Gₗₒw, u, v) + minCut(Gₕᵢgh, u, v)

You are to compute and output this minimum number of removed edges.

inputFormat

The first line contains two integers N and M, representing the number of vertices and the number of edges.

The next M lines each contain three integers u_i, v_i, and w_i describing an edge between vertices u_i and v_i with weight w_i.

The last line contains three integers: u, v and L, where u ≠ v.

outputFormat

Output a single integer — the minimum number of edges that need to be removed so that the new edge (u,v) with weight L can be part of some MST and also part of some MaxST.

sample

3 3
1 2 1
2 3 2
1 3 3
1 3 2

1