Shortest Paths in a Directed Graph

Given a directed graph with n vertices and m edges, and a starting vertex s, compute the shortest path distance from s to every vertex.

The graph is provided in the following format:

• The first line contains three integers: n, m, and s.
• Each of the next m lines contains three integers: u, v, and w, representing a directed edge from vertex u to vertex v with weight w.

You need to output the shortest distance from s to every vertex i (from 1 to n) separated by a space. If a vertex is unreachable from s, output -1 for that vertex.

The mathematical formulation for the shortest distance from s to a vertex i can be described using the following recurrence:

$$ d(s) = 0, \quad d(i) = \min_{(u,i)\in E} \{ d(u) + w(u,i) \} \quad \text{for } i \neq s$$

inputFormat

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

n m s
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• n is the number of vertices.
• m is the number of edges.
• s is the starting vertex.
• Each edge is described by three integers: u (source), v (destination), and w (weight).

outputFormat

Output a single line containing n space-separated integers, where the i-th integer is the shortest path distance from vertex s to vertex i. If vertex i is unreachable from s, output -1 instead.

sample

4 4 1
1 2 5
1 3 3
3 2 1
2 4 2

0 4 3 6