Shortest Paths from the Capital

You are given a kingdom with N cities numbered from 1 to N and M directed roads. Each road connects one city to another and has a non-negative length. The capital city is city 1. Your task is to compute the shortest distance from the capital (city 1) to every other city in the kingdom. If a city is unreachable from the capital, output -1 as its distance.

Input: The first line contains two space-separated integers N and M. Each of the following M lines contains three integers u, v, and w representing a directed road from city u to city v with length w.

Output: Print a single line with N space-separated integers. The i-th integer represents the shortest distance from city 1 to city i, or -1 if city i is unreachable.

Note: The problem can be solved using Dijkstra's algorithm. The weights are non-negative, and if there exists no path from the capital to a city, the answer for that city should be -1.

inputFormat

The first line of input contains two integers N and M. The following M lines each contain three integers u, v, and w, describing a directed road from city u to city v with length w.

outputFormat

Output a single line containing N space-separated integers, where the i-th integer is the minimum distance from city 1 to city i. If city i is unreachable, output -1 instead.## sample

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

0 1 3 8 6