Minimum Cost to Reach All Intersections

In this problem, you are given a directed weighted graph representing a town with intersections. The intersections are labeled from 0 to \(n-1\). You are provided with \(m\) edges, where each edge consists of a starting intersection, an ending intersection, and a travel cost. Given a starting intersection \(s\), your task is to compute the minimum cost required to travel from \(s\) to every other intersection using Dijkstra's algorithm. If an intersection is unreachable from \(s\), output \(-1\) for that intersection.

Input Format: The first line contains three integers \(n\), \(m\), and \(s\) representing the number of intersections, the number of edges, and the starting intersection, respectively. Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), denoting an edge from intersection \(u\) to intersection \(v\) with cost \(w\).

Output Format: Output \(n\) space-separated integers, where the \(i^{th}\) integer represents the minimum cost to reach intersection \(i\) from \(s\). If an intersection is unreachable, output \(-1\) for that intersection.

inputFormat

The first line contains three integers: n (number of intersections), m (number of edges), and s (the starting intersection). The next m lines each contain three integers u, v, and w, representing a directed edge from u to v with weight w.

outputFormat

Output n space-separated integers representing the minimum cost from the starting intersection to each intersection. If an intersection cannot be reached, output -1.## sample

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