Locate Books

You are given a directed weighted graph representing the layout of a library. The nodes in the graph represent shelves, and the edges represent direct paths between shelves with a certain travel time. Starting from a given shelf, your task is to determine the shortest travel times to reach a list of specific shelves that contain books. If a book shelf is not reachable, output -1 for that shelf.

This problem can be modeled using Dijkstra's algorithm. Given the number of shelves \(n\), the number of paths \(m\), and the number of query shelves \(q\), you must compute the minimum travel time from the starting shelf to each book shelf.

Note: The input and output are handled via standard input (stdin) and standard output (stdout) respectively.

inputFormat

The input is read from stdin and is formatted as follows:

 n m q start
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm
 b1 b2 ... bq

Here:

• \(n\) is the number of shelves.
• \(m\) is the number of directed paths.
• \(q\) is the number of books.
• \(start\) is the starting shelf.
• Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) which represent a direct path from shelf \(u\) to shelf \(v\) with travel time \(w\).
• The last line contains \(q\) integers indicating the shelf numbers where the books are located.

outputFormat

Output a single line to stdout containing \(q\) integers separated by spaces. Each integer represents the shortest travel time from the starting shelf to the corresponding book shelf. If a shelf is not reachable, output -1 for that shelf.

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

7 8 7