Problem

Figure 1. The graph from the dataset

The task is to use Dijkstra's algorithm to compute single-source shortest distances in a directed graph with positive edge weights.

Given: A simple directed graph with positive edge weights from $1$ to $10^3$ and $n \le 10^3$ vertices in the edge list format.

Return: An array $D[1..n]$ where $D[i]$ is the length of a shortest path from the vertex $1$ to the vertex $i$ ($D[1]=0$). If $i$ is not reachable from $1$ set $D[i]$ to $-1$.

See Figure 1 for visual example from the sample dataset.

Sample Dataset

6 10
3 4 4
1 2 4
1 3 2
2 3 3
6 3 2
3 5 5
5 4 1
3 2 1
2 4 2
2 5 3

Sample Output

0 3 2 5 6 -1