Galactic Carrier Route Optimization

You are given a galaxy with N space stations and M bidirectional routes connecting them. The central command station is station 1, and your task is to compute the minimum distance required to reach every other station from station 1. If a station is unreachable, output -1 for that station.

Formally, given an undirected weighted graph with nodes \(1,2,\dots,N\) and edges \((u,v,d)\) where \(d\) represents the distance, you must calculate \(dist[i]\) for \(i=2,3,\dots,N\), where \(dist[i]\) is defined as the minimum distance from station 1 to station \(i\), or \(-1\) if no such path exists. You may use Dijkstra's algorithm or any appropriate algorithm.

Input and Output must be handled via standard input (stdin) and standard output (stdout).

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case starts with a line containing two integers \(N\) and \(M\), where \(N\) is the number of stations and \(M\) is the number of routes. The following \(M\) lines each contain three integers \(u\), \(v\) and \(d\), describing a bidirectional route between stations \(u\) and \(v\) with a distance \(d\).

If \(N = 1\), there will be no additional lines for that test case.

outputFormat

For each test case, output a single line containing \(N-1\) space-separated integers. Each integer represents the minimum distance from station 1 to station \(i\) (for \(i=2,3,\dots,N\)). If a station is unreachable, output -1 in its position. For the case where \(N = 1\), output an empty line.

## sample

5
4 4
1 2 6
1 3 4
2 4 5
3 4 2
3 3
1 2 1
2 3 3
3 1 5
4 2
1 2 3
2 3 4
3 0
1 0

6 4 6
1 4
3 7 -1
-1 -1

</p>