Description

There are $n$ cities in Byteland, labeled by $1$ to $n$. The Transport Construction Authority of Byteland is planning to construct $n-1$ bidirectional roads among these cities such that every pair of different cities are connected by these roads directly or indirectly.

The engineering company has offered $m$ possible candidate roads to construct. The $i$-th candidate road will cost $c_i$ dollars, and if it is finally constructed, there will be a road connecting the $u_i$-th city and the $v_i$-th city directly. Fortunately, each road has its discounted price, the $i$-th of which is $d_i$.

The Transport Construction Authority of Byteland can buy at most $k$ roads at their discounted prices. Please write a program to help the Transport Construction Authority find the cheapest solution for $k=0,1,2,\dots,n-1$.

Format

Input

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 1\,000$, $n-1\leq m\leq 200\,000$), denoting the number of cities and the number of candidate roads.

Each of the following $m$ lines contains four integers $u_i,v_i,c_i$ and $d_i$ ($1 \leq u_i,v_i \leq n$, $u_i\neq v_i$, $1\leq d_i\leq c_i\leq 1\,000$), describing a candidate road.

Output

For each test case, output $n$ lines, the $i$-th ($1\leq i\leq n$) of which containing an integer, denoting the cheapest total cost to construct $n-1$ roads when $k=i-1$.

It is guaranteed that the answer always exists.

Samples

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

10
7
6
5
5