Shortest Paths in a Directed Graph

You are given a directed graph with n intersections and m streets. Each street is represented as an edge from intersection u to v with a travel time w. Given a starting intersection s, your task is to determine the shortest travel time from s to every intersection.

If an intersection is unreachable from s, print INF for that intersection.

The problem can be formulated using Dijkstra's algorithm. The algorithm works in \(O((n+m)\log n)\) on sparse graphs.

inputFormat

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

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

Where:

• n is the number of intersections.
• m is the number of streets.
• s is the starting intersection.
• Each of the next m lines contains three integers u, v, and w representing a directed street from intersection u to intersection v with travel time w.

outputFormat

Output a single line containing n values separated by a space, where the i-th value is the shortest travel time from the starting intersection s to intersection i. If an intersection is unreachable, output INF in its place.

## sample

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

0 2 3 4

</p>