You are living in a country which has well-developed transportation. There are $n$ cities numbered from $1$ to $n$ and $m$ public transport routes numbered from $1$ to $m$ in the country. The route numbered $i$ is a directed route from city $u_i$ to city $v_i$, with a cost $a_i$ and a preferential factor $b_i$.
To facilitate people's travel, the government has formulated a series of preferential measures. For a trip that starts from city $s$, passes through routes numbered $e_1, e_2, \dots, e_k$ and ends in city $t$, the cost of each route is calculated as follows:
- For route $e_1$, the cost is $a_{e_1}$.
- For route $e_i \ (i > 1)$, if $a_{e_i} > a_{e_{i - 1}}$, the cost is $a_{e_i} - b_{e_i}$, otherwise the cost is $a_{e_i}$.
The total cost of the trip is the sum of the costs of these routes.
You are now living in city $1$. You want to find the minimum cost of traveling from city $1$ to city $k$, for each $k \in [1, n]$ respectively.
Input
The first line of the input contains an integer $T$ $(1 \leq T \leq 10^4)$, representing the number of test cases.
The first line of each test case contains two integers $n,m$ $(2 \leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5)$, representing the number of cities and routes.
For the following $m$ lines, the $i$-th line contains four integers $u_i, v_i, a_i, b_i$ $(1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq b_i \leq a_i \leq 10^9)$, representing the route numbered $i$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $6 \times 10^5$ and the sum of $m$ does not exceed $1.2 \times 10^6$.
Output
For each test case, output a single line containing $n$ integers separated by a space, the $k$-th of which is the minimum cost of traveling from city $1$ to city $k$, or $-1$ if you can't reach city $k$.
Don't print any extra spaces at the end of each line.