Shortest Paths in a Directed Graph

You are given a weighted, directed graph with \( n \) vertices and \( m \) edges. Each edge is represented by three integers \( u \), \( v \) and \( w \), meaning there is an edge from vertex \( u \) to vertex \( v \) with weight \( w \). Your task is to compute the shortest path from a given starting vertex \( s \) to every other vertex in the graph using Dijkstra's algorithm.

If a vertex is unreachable from \( s \), output INF for that vertex.

The shortest distance of a vertex \( v \) is defined as:

\[ d(v)=\min_{\text{paths } P \text{ from } s \text{ to } v} \sum_{e \in P} w(e), \]

where the sum is taken over the weights of all edges on the path.

Note that the vertices are numbered from 1 to \( n \), and you should output the distances in this order.

inputFormat

The first line of input contains two integers \( n \) and \( m \) where:

• \( n \) is the number of vertices.
• \( m \) is the number of edges.

Then \( m \) lines follow, each containing three integers \( u \), \( v \) and \( w \), representing a directed edge from \( u \) to \( v \) with weight \( w \).

The last line of input contains a single integer \( s \), the starting vertex.

outputFormat

Output a single line containing \( n \) space-separated values. The \( i^{th} \) value should be the shortest distance from vertex \( s \) to vertex \( i \). If vertex \( i \) is unreachable from \( s \), print INF for that vertex.

## sample

5 8
1 2 3
1 3 8
1 5 5
2 4 2
3 5 2
4 3 7
4 5 4
5 2 1
1

0 3 8 5 5