Master Ma Baoguo and a young man are preparing to have a martial arts duel on an undirected graph with $n$ vertices and $m$ edges. Since the young man is worried that Master Ma Baoguo might accuse him of not following martial arts ethics, he needs to improve the competition venue.

For each undirected edge, there are two parameters: the smoothness of the floor $a_i$ and the smoothness of the walls on both sides $b_i$. The young man needs to select exactly $k$ edges and delete all remaining edges.

To prevent Master Ma Baoguo from easily escaping, the young man requires that these $k$ edges do not form a cycle. Furthermore, to prevent Master Ma Baoguo from falling and framing him, the young man requires that the sum of $a_i$ of these $k$ edges multiplied by the sum of $b_i$ of these $k$ edges be as small as possible.

Since he has not yet determined the exact value of $k$, you need to find the answer for all $k$ such that $1 \le k < n$.

Input

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the first line contains two positive integers $n$ and $m$, representing the number of vertices and edges.

The next $m$ lines each contain four positive integers $a_i, b_i, u_i, v_i$, representing the floor smoothness, wall smoothness, and the two vertices connected by the edge.

Output

For each test case, output a single line containing $n-1$ numbers, where the $i$-th number represents the answer for $k=i$.

Examples

Input 1

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

Output 1

2 12 40

Note 1

For $k=1$, the selected edge is $(2,4)$.

For $k=2$, the selected edges are $(2,4), (3,4)$.

For $k=3$, the selected edges are $(2,4), (3,4), (1,2)$.

Subtasks

For all data, it is guaranteed that $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$. The input graph is connected, and for any $1 \le i < j \le m$, either $a_i \neq a_j$ or $b_i \neq b_j$, meaning the pairs $(a_i, b_i)$ are distinct.

Subtask 1 (10 pts): $n, m \le 20, T=1$

Subtask 2 (20 pts): $n-1=m$, i.e., the input edges form a tree, and $n \le 50$

Subtask 3 (20 pts): $n, m \le 50$

Subtask 4 (20 pts): $n-1=m$, i.e., the input edges form a tree.

Subtask 5 (30 pts): No special restrictions.