当前没有测试数据。

4.保留道路

题目描述

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

道路花费的计算公式为$\omega G \times \max\{所有剩下道路的属性g\} + \omega S \times \max\{所有剩下道路的属性s\}$，其中$\omega G$和$\omega S$是给定的值。国王想要在满足连通性的前提下使这个花费最小，现在需要你计算出这个花费。

输入格式

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

第二行包含两个正整数$\omega G$和$\omega S$。

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

输出格式

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

若无论如何不能满足连通性，输出$-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$，$\omega G$，$\omega S$，$g$，$s \leq 1000000000$。

样例

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

30