#P18576. Minimum Spanning Forest

Minimum Spanning Forest

Minimum Spanning Forest

给定一张有 nn 个顶点的无向图,最初没有任何边。顶点编号为 1,2,…,n1,2,\ldots,n。接下来向图中加入 mm 组边。

第 ii 组由四个整数 ui,vi,ℓi,ciu_i,v_i,\ell_i,c_i 描述,其含义是:对每个整数 k∈[0,ℓi−1]k\in[0,\ell_i-1],加入一条连接 ui+ku_i+k 与 vi+kv_i+k、权值为 cic_i 的边。

请在图中选择尽可能多的边,使所选边中不存在环;在边数尽可能多的前提下,最小化这些边的权值总和。也就是说,求最终图的最小生成森林的权值。

每组加入的是两段区间中相同偏移的顶点对,而不是两段之间的所有顶点对。输入允许 ui=viu_i=v_i,也允许不同组产生重复边;自环不能加入无环的森林。图不保证连通,孤立顶点对答案贡献为 00。

输入格式

第一行包含一个整数 tt(1≤t≤1041\le t\le10^4),表示测试组数。

每组测试的第一行包含两个整数 n,mn,m(1≤n,m≤5⋅1051\le n,m\le5\cdot10^5),分别表示顶点数和边组数。

接下来 mm 行,每行包含四个整数 ui,vi,ℓi,ciu_i,v_i,\ell_i,c_i,满足

$$1\le u_i,v_i\le n,\qquad 1\le\ell_i\le n,\qquad 1\le c_i\le10^9,$$

并且

ui+ℓi−1≤n,vi+ℓi−1≤n.u_i+\ell_i-1\le n,\qquad v_i+\ell_i-1\le n.

所有测试的 nn 之和不超过 5⋅1055\cdot10^5。所有测试的 mm 之和也不超过 5⋅1055\cdot10^5,两项总限制分别成立。

输出格式

对每组测试输出一行一个整数,表示最小生成森林的权值。

样例

输入

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