Warehouse Update - Minimum Communication Time

You are given a directed graph representing a network of warehouses connected by communication links. Each warehouse is represented as a node and each communication link as a directed edge from node \(u\) to node \(v\) with an associated time delay \(w\). Given a starting warehouse \(s\), your task is to determine the minimum time required to send an update from warehouse \(s\) to every other warehouse. If a warehouse cannot be reached, output -1 for that warehouse.

The problem can be formally described using the recurrence:

\(d(v) = \min_{(u,v) \in E} (d(u) + w(u,v))\), with \(d(s)=0\) and \(d(v)=\infty\) if \(v\) is unreachable.

Note that warehouses are numbered from 1 to \(n\).

inputFormat

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

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

Where:

• \(n\) is the number of warehouses.
• \(m\) is the number of communication links.
• Each of the next \(m\) lines contains three integers \(u\), \(v\) and \(w\), representing a directed edge from warehouse \(u\) to warehouse \(v\) with time delay \(w\).
• The last line contains the source warehouse \(s\).

outputFormat

Print a single line to standard output containing \(n\) space-separated integers. The \(i\)-th integer represents the minimum time to update warehouse \(i\) from the source warehouse \(s\). If a warehouse is unreachable, print -1 for that warehouse.

## sample

5 6
1 2 2
1 3 4
2 4 7
2 5 1
3 5 5
5 4 3
1

0 2 4 6 3