Dijkstra's Shortest Path

You are given a directed graph with n vertices and m edges. The vertices are numbered from 1 to n. Each edge has an associated weight. Your task is to compute the shortest distance from vertex 1 to every other vertex using Dijkstra's algorithm. If a vertex is unreachable from vertex 1, output -1 for that vertex.

The problem requires using Dijkstra's algorithm, where the distance from vertex 1 to itself is 0, and for every other vertex, the minimum distance is computed. Formally, if we denote the shortest distance to vertex i as \(d_i\), then:

[ d_1 = 0, \quad d_i = \min_{(u,v,w)\in E}{ d_u + w } \quad (\text{for } i \ge 2) ]

You are required to read input from standard input (stdin) and output your result to standard output (stdout).

inputFormat

The first line of input contains two integers n and m (the number of vertices and edges respectively).

The following m lines each contain three integers u, v, and w representing a directed edge from vertex u to vertex v with weight w.

Note that the vertices are numbered from 1 to n.

outputFormat

Output a single line containing n space-separated integers. The i-th integer should be the shortest distance from vertex 1 to vertex i. If vertex i is not reachable from vertex 1, output -1 in its place.

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

0 2 3 9 6