Ma Baoguo 先生とある若者が、$n$ 個の頂点と $m$ 本の辺からなる無向グラフ上で武術の試合を行うことになりました。若者は、Ma Baoguo 先生から「武徳をわきまえていない」と罵られることを恐れ、試合会場を改善することにしました。

各無向辺には、床の滑らかさ $a_i$ と両側の壁の滑らかさ $b_i$ という2つのパラメータがあります。若者はちょうど $k$ 本の辺を選択し、残りのすべての辺を削除する必要があります。

Ma Baoguo 先生が簡単に逃げ出せないように、若者はこれら $k$ 本の辺が閉路を形成しないことを要求します。さらに、Ma Baoguo 先生が転倒して彼をゆすろうとするのを防ぐため、若者はこれら $k$ 本の辺の $a_i$ の総和と $b_i$ の総和の積を最小化したいと考えています。

彼はまだ $k$ がいくつであるかを決定していないため、すべての $1 \le k < n$ について答えを求める必要があります。

入力

最初の行に正整数 $T$ があり、データセットの数を示します。

各データセットについて、最初の行に2つの正整数 $n, m$ があり、それぞれ頂点数と辺数を示します。

続く $m$ 行の各行には、4つの正整数 $a_i, b_i, u_i, v_i$ があり、それぞれその辺の床の滑らかさ、壁の滑らかさ、および接続する2つの頂点を示します。

出力

各データセットについて、$n-1$ 個の数値を1行に出力してください。$i$ 番目の数値は $k=i$ のときの答えを表します。

入出力例

入力 1

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

出力 1

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)}:$ 特殊な制限なし