Given an undirected weighted connected graph $G$, we wish to modify the edge weights such that its minimum spanning tree (MST) is unique. The unit costs for decreasing and increasing the weight of an edge are $a$ and $b$, respectively, and the modified weights must be non-negative integers.
For example, for a graph $G$, if the MST becomes unique after decreasing the weight of one edge by $3$ and increasing the weight of another edge by $2$, the total cost is $3a + 2b$. Calculate the minimum total cost.
Input
The first line contains the data identifier; for the $i$-th test case, the first line contains the string "mst $i$".
The second line contains four positive integers $n, m, a, b$, representing the number of vertices in graph $G$, the number of edges, and the costs to decrease and increase an edge weight by $1$, respectively.
The following $m$ lines each contain three positive integers $x, y, w$, representing an edge between vertex $x$ and vertex $y$ with an initial weight $w$. Vertices are numbered from $1$ to $n$.
Output
Output a single line containing a non-negative integer, which is the required minimum cost. If no modification is needed (i.e., the MST of the graph is already unique), output $0$.
Examples
Input 1
mst 0 4 5 2 3 1 2 1 1 3 1 2 3 1 2 4 2 3 4 2
Output 1
5
Note
After decreasing the weight of edge $(2, 4)$ by $1$ and increasing the weight of edge $(2, 3)$ by $1$, the MST of graph $G$ becomes unique, and the total cost is minimized.
Constraints
| Test Case ID | Constraints |
|---|---|
| 1 | $n \le 7$, $m \le 10$, $a = 10^9$, $b = 1$ |
| 2 | $n \le 50,000$, $m \le 1,000,000$, $a = 10^9$, $b = 1$ |
| 3 | $n \le 100$, $m \le 1,000$, $a = 1$, $b = 10^9$ |
| 4 | $n \le 500,000$, $m \le 1,000,000$, $a = 1$, $b = 10^9$ |
| 5 | .h=6 See the user directory for data |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 |
For 100% of the data, all edges satisfy $1 \le w \le 1,000,000$.