#P18576. Minimum Spanning Forest
Minimum Spanning Forest
Minimum Spanning Forest
给定一张有 个顶点的无向图,最初没有任何边。顶点编号为 。接下来向图中加入 组边。
第 组由四个整数 描述,其含义是:对每个整数 ,加入一条连接 与 、权值为 的边。
请在图中选择尽可能多的边,使所选边中不存在环;在边数尽可能多的前提下,最小化这些边的权值总和。也就是说,求最终图的最小生成森林的权值。
每组加入的是两段区间中相同偏移的顶点对,而不是两段之间的所有顶点对。输入允许 ,也允许不同组产生重复边;自环不能加入无环的森林。图不保证连通,孤立顶点对答案贡献为 。
输入格式
第一行包含一个整数 (),表示测试组数。
每组测试的第一行包含两个整数 (),分别表示顶点数和边组数。
接下来 行,每行包含四个整数 ,满足
$$1\le u_i,v_i\le n,\qquad 1\le\ell_i\le n,\qquad 1\le c_i\le10^9,$$并且
所有测试的 之和不超过 。所有测试的 之和也不超过 ,两项总限制分别成立。
输出格式
对每组测试输出一行一个整数,表示最小生成森林的权值。
样例
输入
4
1 1
1 1 1 1
4 1
1 2 3 1000000000
12 3
1 5 3 4
2 8 4 3
1 7 6 2
20 4
1 9 4 7
5 16 5 10
4 13 3 5
1 2 19 9
输出
0
3000000000
24
151