Two Shortest Paths

The graph has $N$ vertices and $M$ edges. Each edge is directed and has a non-negative integer weight.

For every $2 \le i \le N$, find the minimum total cost of two non-overlapping paths from vertex 1 to vertex $i$. Two paths do not overlap if they share no edge. The cost of a path is the sum of the weights of the edges on it.

The first line contains the number of test cases $TC$. Each of the following $TC$ test cases is given on separate lines.

Each test case has the following format.

• The first line contains two integers $N$ and $M$.
• Each of the next $M$ lines contains three integers $u_i$, $v_i$, $w_i$. This means there is an edge from vertex $u_i$ to vertex $v_i$ with weight $w_i$.

For each test case, print one line with $N-1$ integers. The $i$-th integer is the minimum total cost of two non-overlapping paths from vertex 1 to vertex $i+1$. If two non-overlapping paths do not exist, print -1.

• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• $i \neq j \iff (u_i, v_i) \neq (u_j, v_j)$
• $0 \le w_i \le 10^9$
• Vertex 1 can reach every vertex.
• In one input file, the sum of $N$ is at most $100\,000$.
• In one input file, the sum of $M$ is at most $1\,000\,000$.