1013: 抗震救灾

题目描述

近日，由于一场世纪大地震，某国通讯设施全面瘫痪。在灾后重建中，抢修通讯设备成为首要任务。现在，你已经了解该国的基本状况，该国首脑希望你设计一种方案，使得所用的救灾资金尽可能少。

已知该国地形可以简化成包含$n$个点的一张无向图，每个点代表一座城市。由于地震的破坏，该国的城市之间已经只剩下$m$条仍具备通行条件的双向道路。当然，目前该国的所有城市是联通的。现在，该国希望在一些仍能通行的道路下铺设通信电缆，使得任意两个城市之间能够通过通信电缆直接或间接地传递灾情。不过，若某条道路被破坏后，该国的所有城市不再全部联通，则这条道路被认为是危险道路，因为一旦这条道路被次生灾害破坏，那么相应的通信电缆也会被破坏，而且没有其他可供选择的途径来恢复通信。在这样的危险道路上，你只能选择用无线通信设备代替。（注意：在非危险道路上，即使无线设施的费用低于通信电缆的费用，你也只能铺设通信电缆，因为这种方式可靠性更高。）

输入格式

第一行包含两个正整数$n$和$m$。

接下来共$m$行，第$i$行包含四个整数$s_i$，$t_i$，$a_i$和$b_i$，分别表示第$i$条道路连接的两座城市，以及在该条道路上铺设电缆和架设无线设备的费用。

输出格式

第一行包含一个整数，表示最小代价。

样例输入

8 11 2 6 0 9 2 7 8 6 7 3 4 0 4 8 3 0 4 5 0 0 4 1 1 10 2 4 0 10 7 6 0 10 2 3 2 1 1 4 1 0 1 5 2 4

样例输出

13

数据范围

对于$30\%$的数据，$n \le 500$，$m \le 3000$。
对于额外$40\%$的数据，数据保证不存在危险道路。
对于$100\%$的数据，$n \le 10^{5}$，$m \le 5 \times 10^{5}$。
在每一部分数据中，均包含若干较小的测试点。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！