题目描述

注意这题和在集训队 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

数据范围与提示

对于所有数据，保证 $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)}:$ 无特殊限制。