#3412. 「2020-2021 集训队作业」不讲武德

题目描述

注意这题和在集训队 OJ 上的版本不同，数据范围部分分都有改动，并且为了卡掉乱搞，这里需要多测。

马宝锅老师和一位年轻人准备在一张 $n$ 个点、$m$ 条边的无向图上比武。由于年轻人担心马宝锅老师骂他不讲武德，因此他需要改进一下比赛场地。

对于每条无向边，有两个参数：地板的光滑度 $a_i$ 以及两侧墙的光滑度 $b_i$。年轻人需要选出恰好 $k$ 条边，并删掉剩下所有的边。

为了不让马宝锅老师会方便逃跑，年轻人要求这 $k$ 条边不形成环。此外，为了不让马宝锅老师摔倒来讹他，年轻人要求这 $k$ 条边的 $a_i$ 之和乘以 $b_i$ 之和尽量小。

由于他还没有确定 $k$ 到底是多少，因此你需要对于 $1 \le k < n$ 的所有 $k$ 求出答案。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行两个正整数 $n,m$，表示点数和边数。

接下来 $m$ 行每行四个正整数 $a_i,b_i,u_i,v_i$，表示这条边的地板光滑度、墙的光滑度以及连接的两个点。

输出格式

对于每组数据输出一行 $n-1$ 个数字，第 $i$ 个数字表示 $k=i$ 时的答案。

样例

输入

1
4 5
2 3 1 2
5 6 1 3
6 1 3 4
4 1 3 4
2 1 2 4

输出

2 12 40

解释
$k=1$ 时，选的边是 $(2,4)$。
$k=2$ 时，选的边是 $(2,4),(3,4)$。
$k=3$ 时，选的边是 $(2,4),(3,4),(1,2)$。

数据范围与提示

对于所有数据，保证 $n-1 \le m \le 1500$，$\sum m^2 \le 2.5\times10^6$，$1 \le u_i,v_i \le n$，$u_i \neq v_i$，$1 \le a_i,b_i \le 2\times10^6$，输入的图是连通图，并且对于任意的 $1 \le i < j \le m$，都有 $a_i \neq a_j$ 或者 $b_i \neq b_j$，即二元组 $(a_i,b_i)$ 两两不同。

• $\text{subtask1(10pts)}: n,m \le 20, T=1$
• $\text{subtask2(20pts)}: n-1=m$，即输入的边构成一棵树，且 $n \le 50$
• $\text{subtask3(20pts)}: n,m \le 50$
• $\text{subtask4(20pts)}: n-1=m$，即输入的边构成一棵树
• $\text{subtask5(30pts)}:$ 无特殊限制