Dijkstra Shortest Path

Given a directed graph with non-negative edge weights, find the shortest distance from a source vertex S to every vertex.

Input Format

The first line contains two integers V and E. Each of the next E lines contains a directed edge u v w (from u to v with weight w). The last line contains the source vertex S.

Output Format

Print V space-separated integers: the shortest distance from S to vertex 0, 1, ..., V-1. Use -1 for a vertex that cannot be reached.