Public Transport System

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.

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$.

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.

2
4 4
1 2 3 2
2 3 4 1
1 3 7 5
4 3 2 1
4 8
4 2 3 3
1 3 6 3
4 2 10 5
1 2 8 2
3 2 4 3
4 2 7 7
3 4 4 2
1 2 8 1

0 3 6 -1
0 8 6 10

2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛（重赛）