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 1

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.