Single Source Shortest Paths

You are given a directed weighted graph with \(V\) vertices and \(E\) edges. Each edge is represented as a triplet \( (u, v, w) \) where \(u\) is the starting vertex, \(v\) is the ending vertex, and \(w\) is the weight of the edge. Your task is to compute the shortest distance from a given source vertex to every other vertex using Dijkstra's algorithm.

If a vertex is unreachable from the source, output INF for that vertex.

Note: The vertices are numbered from 0 to \(V-1\).

inputFormat

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

V E source
u1 v1 w1
u2 v2 w2
... 

Where:

• V is the number of vertices.
• E is the number of edges.
• source is the starting vertex.
• Each of the next E lines contains three integers \(u\), \(v\), \(w\) representing an edge from vertex \(u\) to vertex \(v\) with weight \(w\).

outputFormat

Output the shortest distances from the source to every vertex in a single line, separated by a space. For unreachable vertices, output INF. The output is printed to stdout.

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

0 2 3 9 6