Shortest Paths from the Central Station

You are given an undirected weighted graph representing roads connecting intersections. The intersections are numbered from 1 to n, where node 1 is the central station. Each road connects two intersections and has an associated travel time.

Your task is to compute the shortest travel time from the central station (intersection 1) to every other intersection. If an intersection is unreachable from the central station, output -1 for that intersection.

This problem can be efficiently solved using Dijkstra's algorithm. The weight (travel time) of each road is positive. Formally, for each intersection i (where 2 \le i \le n), determine the minimum travel time from intersection 1 to i, or output -1 if no such path exists.

In mathematical notation, if you denote the travel time on a path as \(t_{path}\), you need to find:

[ \min_{\text{path }1\rightarrow i} ; t_{path} ]

where the minimization is taken over all possible paths from 1 to i. If there is no valid path, then the answer is -1.

inputFormat

The first line contains two integers n and m, where n is the number of intersections and m is the number of roads. The following m lines each contain three space-separated integers u, v, and t indicating that there is a bidirectional road connecting intersections u and v with a travel time of t.

Note: It is guaranteed that all travel times are positive integers.

outputFormat

Output a single line containing n-1 space-separated integers. The i-th integer (for i = 2, 3, ..., n) should represent the shortest travel time from intersection 1 to intersection i. If intersection i is unreachable, output -1 for that intersection.

## sample

4 4
1 2 4
1 3 2
2 3 5
3 4 1

4 2 3