Shortest Data Transmission Time

This problem involves computing the shortest time required to send data from a source node to all other nodes in a directed network. Each edge in the network takes a constant time \(T\) to traverse. Given the network structure, you need to determine the minimum time to reach each node starting from the source node \(S\). If a node is unreachable, output -1 for that node.

The task is to compute the shortest transmission time for each node. Formally, if we denote the time to traverse an edge as \(T\), then the shortest time \(D[i]\) to reach node \(i\) from node \(S\) is defined as:

$$D[i] = \begin{cases} 0 & \text{if } i = S,\\ \min_{(u, i) \in E}\{D[u] + T\} & \text{if } i \text{ is reachable from } S,\\ -1 & \text{otherwise.} \end{cases} $$

Your solution should read the network information from the standard input and print the shortest times for all nodes in order.

inputFormat

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

• The first line contains three integers: \(T\) (the constant time per link), \(N\) (the number of nodes), and \(M\) (the number of directed links).
• The next \(M\) lines each contain two integers \(U\) and \(V\), indicating a directed link from node \(U\) to node \(V\).
• The last line contains an integer \(S\), the source node.

Nodes are 0-indexed.

outputFormat

Output a single line with \(N\) space-separated integers. The \(i\)-th integer should represent the shortest time required to send data from node \(S\) to node \(i\). If node \(i\) is unreachable, print -1 for that node.

## sample

10 5 6
0 1
0 2
1 3
1 4
2 3
3 4
0

0 10 10 20 20