B. Expensive Transport
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Barcelona, a new anti-Baq tax has been approved. This tax means that every time Baq moves using public transport, he has to pay not only the cost of going from one stop to the next at each stop but also the total cost of the journey he has already made from the origin to the current stop (defined as the sum of the "normal" costs of each transport between stops, not what Baq has actually paid).

For example, if he makes a journey of five stops (let's say $$$A, B, C, D, E$$$) and the costs of the journeys between stops are $$$AB = 1, BC = 2, CD = 1, DE = 3$$$, then the total cost for Baq will be $$$15$$$: at $$$A$$$ he will pay $$$1$$$ to go to $$$B$$$; at $$$B$$$ he will pay $$$2$$$ to go to $$$C$$$ plus $$$1$$$, which is the cost of the journey $$$AB$$$; at $$$C$$$ he will pay $$$1$$$ to go to $$$D$$$ plus $$$3$$$, which is the cost of the journey $$$ABC$$$ ($$$1+2$$$); at $$$D$$$ he will pay $$$3$$$ to go to $$$E$$$ plus $$$4$$$, which is the cost of the journey $$$ABCD$$$ ($$$1+2+1$$$).

Baq does not like this tax, but he will not give up the transport service. Baq asks you to help him find the minimum cost of a journey between stop $$$0$$$ and each of the other $$$n-1$$$ stops.

Input

The input starts with an integer $$$T$$$, the number of cases. Each case begins with two integers $$$n$$$ and $$$m$$$, the number of stops and the number of connections between stops. This is followed by $$$m$$$ lines with three integers $$$u_i, v_i, w_i$$$, indicating that there is a connection from stop $$$u_i$$$ to stop $$$v_i$$$ with a price of $$$w_i$$$. The stops are numbered from $$$0$$$ to $$$n-1$$$. The connections between stops are directed, meaning that the connection from $$$u$$$ to $$$v$$$ is not the same as the connection from $$$v$$$ to $$$u$$$.

Output

For each case, write on a line with $$$n-1$$$ integers, the $$$i$$$-th (starting from $$$1$$$) of which is the cost for Baq of the journey between station $$$0$$$ and station $$$i$$$. If he cannot reach station $$$i$$$, write $$$-1$$$.

Scoring

$$$1 \leq T \leq 100$$$

$$$3 \leq n, m \leq 1000$$$. The sum of $$$n+m$$$ for all cases is less than $$$3 \cdot 10^4$$$.

$$$0 \leq u_i, v_i \leq n-1, 1 \leq w_i \leq 1000$$$

22 points: $$$n \leq 10, m \leq 20$$$, the sum of $$$n+m$$$ for all cases is less than $$$800$$$.

11 points: $$$w_i = 1$$$ for $$$i = 1, \ldots, m$$$

14 points: Each stop is only connected to the previous and the next (cyclically). Formally, $$$m = 2n$$$ and $$$u_{2i} = u_{2i-1} = i-1, v_{2i} = i-2, v_{2i-1} = i$$$ for all $$$i$$$ except edges $$$2$$$ and $$$2n-1$$$, which are $$$u_2 = 0, v_2 = n-1$$$ and $$$u_{2n-1} = n-1, v_{2n-1} = 0$$$.

29 points: $$$n, m \leq 80$$$, the sum of $$$n+m$$$ for all cases is less than $$$2500$$$.

24 points: No additional restrictions.

Example
Input
4
4 4
0 1 1
1 2 1
2 3 1
0 3 5
4 4
0 1 1
1 2 1
2 3 1
0 3 7
5 5
0 1 1
1 2 2
2 4 1
0 3 2
3 4 3
5 6
0 2 7
1 3 9
2 1 3
3 0 1
3 1 1
4 3 4
Output
1 3 5 
1 3 6 
1 4 2 7 
17 7 36 -1