Minimum Time to Reach Galleries

You are given n galleries, numbered from 0 to n-1, and m passages connecting them. Each passage is described by three integers u, v, and t indicating there is a unidirectional passage from gallery u to gallery v that takes t time to traverse.

Your task is to compute the minimum time required to reach every gallery starting from gallery 0. If a gallery is not reachable from gallery 0, output -1 for that gallery.

The problem can be mathematically formulated as:

$$\text{dist}[0] = 0,\quad \text{and} \quad \text{dist}[v] = \min_{\substack{(u,v,t) \in passages}} \{ \text{dist}[u] + t \},$$

where if there is no path from 0 to v, then \(\text{dist}[v] = -1\).

inputFormat

The input is read from standard input (stdin) and is in the following format:

n m
u1 v1 t1
u2 v2 t2
... (m lines total)

Here, the first line contains two integers, n (the number of galleries) and m (the number of passages). Each of the following m lines contains three space-separated integers: u, v, and t, representing a passage from gallery u to gallery v with travel time t.

outputFormat

The output should be written to standard output (stdout). It consists of a single line with n space-separated integers. The i-th integer denotes the minimum time required to reach gallery i from gallery 0. If gallery i is not reachable, output -1 for that gallery.

## sample

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

0 2 3 9 6