Single Source Shortest Path

You are given a weighted directed graph with n nodes and m edges. Each edge has a nonnegative weight. Your task is to compute the shortest distance from a given source node \( s \) to every other node. It is guaranteed that every node is reachable from \( s \).

Note: The nodes are numbered from 1 to \( n \). Use an appropriate algorithm such as Dijkstra's algorithm.

inputFormat

The first line contains three integers \( n \), \( m \), and \( s \) (the number of nodes, the number of edges, and the source node respectively).

Then \( m \) lines follow, each containing three integers \( u \), \( v \), and \( w \) indicating there is a directed edge from node \( u \) to node \( v \) with weight \( w \) (\( w \ge 0 \)).

outputFormat

Output a single line containing \( n \) integers, where the \( i^{th} \) integer represents the shortest distance from the source node \( s \) to node \( i \). The distances should be printed in order from node 1 to node \( n \), separated by spaces.

sample

3 3 1
1 2 1
1 3 2
2 3 1

0 1 2