9214 - 代价之和的最小值

给定无向带权连通图G,我们希望通过修改边的权值,使它的最小生成树唯一,已知减小,增加一条边的权值的单位代价分别为 a 和 b,且修改后的权值必须为非负整数。 例如,对某个图G,如果将一条边的权值减 3,另一条边的仅值加 2 之后,它的最小生成树唯一,则此时的代价之和是 3a+2b。试计算代价之和的最小值。

输入

从文件mst.in中读入数据。 第一行包含字符串“mst” 和数据编号。 第二行包含 4 个正整数 n,m,a,b,分别表示图 G 顶点的个数,边的条数,以及对一条边的权值减小 1,增加 1 的代价。 接下来 m 行,每行 3 个正整数 x,y,w,表示顶点 x 和顶点 y 之间有一条初始权值为 w 的边。 顶点由 1 至 n 编号。

输出

输出到文件mst.out中。 输出文件仅一行,包含一个整数,表示最小代价,无需修改则输出 0。

样例

输入

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

输出

5
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题