#Psmt18. 4.保留道路

4.保留道路

4.保留道路

题目描述

有个国家有N个城市,城市由1,2,3,...,N标号,城市间有M条双向道路,每条道路都有两个属性g和s,两个城市间可能有多条道路,并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因,国王不得不下令减小花费从而关闭一些道路,但是必须要保证任意两个城市相互可达。

道路花费的计算公式为wGmax{所有剩下道路的属性g}+wSmax{所有剩下道路的属性s},其中wG和wS是给定的值。国王想要在满足连通性的前提下使这个花费最小,现在需要你计算出这个花费。

输入格式

第一行包含两个正整数N和M。

第二行包含两个正整数wG和wS。

后面的M行每行描述一条道路,包含四个正整数u,v,g,s,分别表示道路连接的两个城市以及道路的两个属性。

输出格式

输出一个整数,表示最小花费。

若无论如何不能满足连通性,输出-1。

数据范围

(原站未提供,导入后需人工补齐)

样例

3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1
30

提示

对于10%的数据,N<=10,M<=20;

对于30%的数据,N<=100,M<=1000;

对于50%的数据,N<=200,M<=5000;

对于100%的数据,N<=400,M<=50000,wG,wS,g,s<=10 0000 0000。