馬寶國老師和一位年輕人準備在一張 $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

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

說明 1

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