SP10645 MYQ7 - The Rail Network Renovation

美丽的图瓦克斯国拥有一个古老的铁路网络，这个网络由 $n$ 个城市和 $m$ 条铁轨连接而成。图瓦克斯国王命令铁道部长 Poopsie 对整个铁路系统进行翻新。由于 Poopsie 曾经的懒散，这些铁轨状态糟糕，因此他准备修复部分铁轨，同时完全拆除其他一些铁轨。 国王希望在翻新完成后，所有城市之间仍可以互相连通。不过，国王也想省钱，所以希望用最少的花费实现这个目标。请帮助 Poopsie 找到翻新整个铁路网络的最小花费。

第一行包含整数 $t$，表示测试用例的数量（$1 \le t \le 100$）。 每个测试用例的第一行包含两个整数：城市数量 $n$（$1 \le n \le 1000$）和铁轨数量 $m$（$0 \le m \le 1000000$）。接下来的 $m$ 行描述了每条铁轨以及其对应的拆除和重建费用。这 $m$ 行中的每一行包含四个整数 $a, b, d, r$（$1 \leq d, r \leq 1000000$），表示连接城市 $a$ 和城市 $b$ 的一条铁轨，其中拆除费用为 $d$，重建费用为 $r$（城市编号从 1 到 $n$）。

对于每个测试用例，输出一行结果，即完成整个铁路网络翻新所需的最少资金。每行包含一个整数。 **本翻译由 AI 自动生成**