Minimum Travel Cost from the Capital

You are given a directed weighted graph representing a network of towns. The towns are numbered from 1 to n, and there are m one-way roads connecting them. Each road is described by three integers u, v, and c indicating that there is a road from town u to town v with cost c.

Your task is to compute the minimum travel cost from the capital (town 1) to every other town. If a town is unreachable from the capital, output -1 for that town.

The problem can be formalized using Dijkstra's algorithm. The cost to travel from town 1 to town i is defined as:

$$\text{cost}(i)=\min_{\text{paths from 1 to } i}\sum_{\text{edge }(u,v)\in\text{path}} c(u,v), $$

where if town i is unreachable, we define \(\text{cost}(i)=-1\).

inputFormat

The input is given via stdin and consists of the following:

• The first line contains two integers n and m, where n is the number of towns and m is the number of one-way roads.
• Each of the following m lines contains three integers u, v, and c representing a road from town u to town v with cost c.

outputFormat

Print a single line containing n-1 space-separated integers. The i-th integer represents the minimum travel cost from the capital (town 1) to town i+1. If a town is unreachable, output -1 in its place.

## sample

4 5
1 2 10
1 3 20
2 3 5
2 4 1
3 4 1

10 15 11

</p>