Taco: Shortest Paths in a Graph

You are given an undirected weighted graph with \(n\) cities (numbered from 1 to \(n\)) and \(m\) roads. Each road connects two distinct cities and has a non-negative weight. Given a starting city, your task is to compute the shortest path from the starting city to every other city.

If a city is unreachable from the starting city, output -1 for that city.

Note: The graph is represented by its cities and roads. Use Dijkstra's algorithm, which is based on the following recurrence:

\( d(v) = \min\{ d(u) + w(u, v) \}\) for every edge \((u,v)\), with \(d(start)=0\).

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of cities and \(m\) is the number of roads.
• The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\), indicating that there is a road between city \(u\) and city \(v\) with weight \(w\).
• The last line contains one integer, the starting city.

It is guaranteed that \(1 \leq u, v \leq n\) and \(w \geq 0\).

outputFormat

Print a single line to stdout with \(n\) space-separated integers, where the \(i\)-th integer is the shortest distance from the starting city to city \(i\). If city \(i\) is unreachable, output -1 instead.

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

0 3 4 5 6