Secsa's MST Edge Guarantee

Secsa is fascinated by minimum spanning tree problems. In an undirected graph with n vertices and m edges, there may exist several different minimum spanning trees (MSTs). For example, the figure below shows several MSTs of the same graph.

However, today you are not asked to find an MST. Instead, Secsa wants to know: for a given edge AB in the graph, what is the minimum cost required to force the edge AB to be included in every MST of the graph. To achieve this, you are allowed to perform the following operation any number of times.

Operation: Select any edge P₁P₂ in the graph. Then, for every other edge (i.e. all edges except P₁P₂), reduce its weight by 1. Each such operation costs 1.

Your task is to determine the minimum total cost (i.e. the minimum number of operations) needed to modify the graph so that the special edge AB is guaranteed to be part of every MST of the graph.

Hint: An edge e is present in every MST if and only if for every cycle containing e, e is the unique lightest edge in that cycle. In this problem, you can lower the weight of edge AB by letting it get reduced in every operation, while you can choose to protect a competing edge (by selecting it in the operation) so that its weight remains unchanged. In effect, for the special edge with original weight \(w_{AB}\), if after \(x\) operations its final weight becomes \(w_{AB} - x\), you want that for every cut (separating A and B) there is at least one alternative crossing edge whose final weight is strictly greater than \(w_{AB} - x\>.

Observe that if you choose an alternative edge with a high original weight and protect it in every operation (so that its weight remains unchanged), then for the cut defined by the special edge, the condition to force AB into every MST becomes:

\[ w_{AB} - x < d \quad,\quad d = \text{(the chosen alternative edge's weight)}. \]

Since you may pick the best alternative edge among those crossing the cut (i.e. the one with the maximum weight), the answer is determined by the following formula:

\[ \text{cost} = \max(0, w_{AB} - d + 1), \]

where \(d\) is the maximum, over all simple paths from A to B in the graph after removing the special edge AB, of the minimum edge weight along that path (the so-called max–min value). Notice that if there is no alternative path from A to B (i.e. AB is a bridge), the answer is 0 because AB is already included in every MST.

Input Format: The input begins with two integers n and m on the first line, indicating the number of vertices and edges. The second line contains two integers A and B which denote the endpoints of the special edge AB. Then follow m lines, each containing three integers u, v, and w denoting an undirected edge between vertices u and v with weight w. It is guaranteed that the special edge AB appears in the list of edges.

Output Format: Output a single integer: the minimum cost (number of operations) required to guarantee that the special edge AB is part of every MST of the graph.

inputFormat

The first line contains two positive integers n and m (\(1 \leq n \leq 10^5\), \(1 \leq m \leq 10^5\)). The second line contains two integers A and B (\(1 \leq A, B \leq n\)) representing the endpoints of the special edge.

Each of the following m lines contains three integers u, v, and w (\(1 \leq u, v \leq n, 1 \leq w \leq 10^9\)), indicating there is an undirected edge between u and v with weight w. It is guaranteed that the special edge AB is among these edges.

outputFormat

Output a single integer which is the minimum cost (i.e., the minimum number of operations required) so that the special edge AB is guaranteed to appear in every minimum spanning tree of the graph.

sample

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

3