Shortest Paths from Vertex 1

You are given a directed graph with \(N\) vertices and \(M\) weighted edges. The graph is described by a list of edges, where each edge is given by three integers \(u\), \(v\), and \(w\), representing a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\). Your task is to compute the shortest path from vertex 1 to every other vertex (i.e. vertices 2 through \(N\)).

If a vertex is unreachable from vertex 1 then its shortest distance should be reported as -1. Use Dijkstra's algorithm to solve the problem efficiently.

The problem can be mathematically stated as follows:

\[ \text{For each vertex } i \ (2 \le i \le N):\quad d(i) = \min_{\text{paths }1 \to i} \sum\, \text{edge weights},\quad \text{if no path exists, } d(i) = -1. \]

inputFormat

The first line of input contains two integers \(N\) and \(M\), where \(N\) is the number of vertices and \(M\) is the number of edges.

The next \(M\) lines each contain three integers \(u\), \(v\) and \(w\), indicating that there is a directed edge from vertex \(u\) to vertex \(v\) with weight \(w\).

Input is provided via standard input (stdin).

outputFormat

Output a single line consisting of \(N-1\) space-separated integers. Each integer represents the shortest distance from vertex 1 to vertex \(i\) (for \(2 \le i \le N\)). If a vertex is unreachable, output -1 for that vertex.

Output should be printed to standard output (stdout).

## sample

5 6
1 2 2
1 3 4
2 3 1
3 4 1
2 4 7
5 3 5

2 3 4 -1