暂无测试数据。

题目描述

给定无向带权连通图\(G\)，
我们希望通过修改边的权值，
使它的最小生成树唯一。

已知减小、增加一条边的权值的单位代价分别为 \(a\) 和 \(b\)，
且修改后的权值必须为非负整数。

例如，对某个图 \(G\)，
如果将一条边的权值减 3、
另一条边的权值加2之后，
它的最小生成树唯一，
则此时的代价之和是 \(3a+2b\)。
试计算代价之和的最小值。

输入

第一行，包含数据编号，对于第\(i\)个数据，第一行将包含字符串 “mst i”。
第二行，包含 4 个正整数 \(n,m,a,b\)，
分别表示图 \(G\) 顶点的个数、边的条数，
以及对一条边的权值减 1、加 1 的代价。

接下来 \(m\) 行，
每行 3 个正整数 \(x,y,w\)，
表示顶点 \(x\) 和顶点 \(y\) 之间连有一条初始权值为 \(w\) 的边。
顶点由 1 至 \(n\) 编号。

输出

一行，包含一个非负整数，即要求的最小值。
如果无需修改，即图本身的最小生成树就是唯一的，则输出 0。

样例输入

mst 0
4 5 2 3
1 2 1
1 3 1
2 3 1
2 4 2
3 4 2

样例输出

5

数据范围限制

时限和内存限制

每个测试点时限：4秒
内存限制：256MB