Mistrz Ma Baoguo i pewien młodzieniec przygotowują się do pojedynku na grafie nieskierowanym o $n$ wierzchołkach i $m$ krawędziach. Ponieważ młodzieniec obawia się, że mistrz Ma Baoguo oskarży go o brak zasad (wushu), musi on nieco ulepszyć miejsce zawodów.

Dla każdej krawędzi nieskierowanej określone są dwa parametry: gładkość podłogi $a_i$ oraz gładkość ścian po obu stronach $b_i$. Młodzieniec musi wybrać dokładnie $k$ krawędzi i usunąć wszystkie pozostałe.

Aby mistrz Ma Baoguo nie mógł łatwo uciec, młodzieniec wymaga, aby te $k$ krawędzi nie tworzyło cyklu. Ponadto, aby mistrz Ma Baoguo nie przewrócił się i nie wyłudził odszkodowania, młodzieniec chce, aby iloczyn sumy wartości $a_i$ oraz sumy wartości $b_i$ dla wybranych $k$ krawędzi był jak najmniejszy.

Ponieważ nie ustalono jeszcze wartości $k$, musisz wyznaczyć odpowiedź dla wszystkich $k$ w zakresie $1 \le k < n$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$, oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych, pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$, oznaczające liczbę wierzchołków i krawędzi.

Następnie $m$ linii zawiera po cztery liczby całkowite $a_i, b_i, u_i, v_i$, oznaczające odpowiednio gładkość podłogi, gładkość ścian oraz dwa wierzchołki połączone krawędzią.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii $n-1$ liczb, gdzie $i$-ta liczba oznacza odpowiedź dla $k=i$.

Przykład

Przykład 1

Wejście

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

Wyjście

2 12 40

Uwagi

Dla $k=1$ wybrano krawędź $(2,4)$.

Dla $k=2$ wybrano krawędzie $(2,4), (3,4)$.

Dla $k=3$ wybrano krawędzie $(2,4), (3,4), (1,2)$.

Podzadania

Dla wszystkich danych wejściowych gwarantuje się, że $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$. Graf wejściowy jest spójny, a dla dowolnych $1 \le i < j \le m$ zachodzi $a_i \neq a_j$ lub $b_i \neq b_j$, co oznacza, że pary $(a_i, b_i)$ są parami różne.

• $\text{subtask1(10 pkt)}: n, m \le 20, T=1$
• $\text{subtask2(20 pkt)}: n-1=m$, czyli krawędzie tworzą drzewo, $n \le 50$
• $\text{subtask3(20 pkt)}: n, m \le 50$
• $\text{subtask4(20 pkt)}: n-1=m$, czyli krawędzie tworzą drzewo
• $\text{subtask5(30 pkt)}:$ brak dodatkowych ograniczeń