409371: GYM103492 I 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