Unique Minimum Spanning Tree Adjustment

Given an undirected weighted connected graph (G=(V,E)) with integer weights (w_i) on each edge, you are allowed to modify the weight of any edge at a cost. Decreasing an edge's weight by one unit costs (a) while increasing it by one unit costs (b). The modified weight must be a nonnegative integer. You need to modify the weights such that the graph's minimum spanning tree (MST) becomes unique and the total modification cost is minimized. For instance, if by decreasing one edge's weight by 3 units and increasing another edge's weight by 2 units the MST becomes unique, the total cost is (3a+2b).


Hint: A valid strategy is to choose a spanning tree (T) and force all its edges to the same value (k) while setting every edge not in (T) to a value of at least (k+1). Then, the cost for a tree edge with original weight (w) becomes (\begin{cases} (w-k)a & \text{if } k \le w\ (k-w)b & \text{if } k>w \end{cases}) and for every non-tree edge with original weight (w) the target becomes (k+1) with cost defined similarly. By choosing the original MST of (G) as (T) and optimizing over (k) (which can be chosen among candidate breakpoints derived from the edge weights), one can obtain an optimal solution.

inputFormat

The first line contains four integers: \(n\), \(m\), \(a\), and \(b\) — the number of vertices, the number of edges, the unit cost for decreasing an edge's weight, and the unit cost for increasing an edge's weight, respectively.

Each of the next \(m\) lines contains three integers: \(u\), \(v\), and \(w\), indicating that there is an edge between vertices \(u\) and \(v\) with weight \(w\).

You may assume that the given graph is connected.

outputFormat

Output a single integer, the minimum total cost required to modify the weights so that the graph's MST becomes unique.

sample

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

1