题目描述
有个国家有 $N$ 个城市，城市由 $1,2,3,\cdots,N$ 标号，城市间有 $M$ 条双向道路，每条道路都有两个属性 $g$ 和 $s$，两个城市间可能有多条道路，并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因，国王不得不下令减小花费从而关闭一些道路，但是必须要保证任意两个城市相互可达。
道路花费的计算公式为 $wG\* max \{ 所有剩下道路的属性g\} + wS \* max \{所有剩下道路的属性s\} $ ，其中 $wG$ 和 $wS$ 是给定的值。国王想要在满足连通性的前提下使这个花费最小，现在需要你计算出这个花费。
输入
第一行包含两个正整数 $N$ 和 $M$。
第二行包含两个正整数 $wG$ 和 $wS$。
后面的 $M$ 行每行描述一条道路，包含四个正整数 $u,v,g,s$，分别表示道路连接的两个城市以及道路的两个属性。
输出
输出一个整数，表示最小花费。
若无论如何不能满足连通性，输出 $-1$。
样例输入输出
输入#1
复制
3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1
提示
对于 $10\%$ 的数据，$N \leq 10$，$M \leq 20$；
对于 $30\%$ 的数据，$N \leq 100$，$M \leq 1000$；
对于 $50\%$ 的数据，$N \leq 200$，$M \leq 5000$；
对于 $100\%$ 的数据，$N \leq 400$，$M \leq 50000$，$wG,wS,g,s \leq 10^9$。