Minimum Time for Critical Microservices

You are given a directed weighted graph representing a network of microservices. Each edge (a, b, t) indicates that microservice a can call microservice b in t time units. Given a starting microservice s and a set of k critical microservices, your task is to compute the minimum time required to reach each critical microservice from s.

If a critical microservice is not reachable from s, output -1 for that service.

The problem can be formulated using the famous Dijkstra's algorithm. In mathematical form, for a given start node \( s \) and any other node \( v \), you must compute the minimum distance \( d(v) \), where:

[ d(v) = \min_{\text{path from } s \text{ to } v} \sum_{(u, w) \in \text{path}} t_{uw} ]

You must process input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of microservices and the number of dependency calls, respectively.

The next \( m \) lines contain three integers each: \( a\), \( b\), and \( t \) representing an edge from microservice \( a \) to microservice \( b \) with a call time of \( t \) units.

The following line contains an integer \( s \), the starting microservice.

The next line contains an integer \( k \) indicating the number of critical microservices.

The last line contains \( k \) space-separated integers which are the indices of the critical microservices.

outputFormat

Output a single line with \( k \) space-separated integers where each integer is the minimum time required to reach the corresponding critical microservice from \( s \). If a critical microservice is unreachable, output -1 for that microservice.

## sample

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

12 5