Shortest Travel Times

You are given a network of cities and bidirectional roads connecting them. The cities are numbered from 1 to n and each road has an associated travel time. City 1 is the warehouse city. Your task is to determine the shortest travel time from city 1 to a set of destination cities. If a destination city is unreachable from city 1, output -1 for that city.

The problem can be formulated using the following notation:

( n ): Number of cities ( m ): Number of roads ( (u, v, w) ): A bidirectional road between cities ( u ) and ( v ) with travel time ( w ) ( q ): Number of destination cities ( destinations ): The list of destination cities

The shortest travel times must be computed using an efficient algorithm such as Dijkstra's algorithm.

Input Format:

• The first line contains two integers \( n \) and \( m \).
• The next \( m \) lines each contain three integers \( u \), \( v \), \( w \) indicating a road.
• The following line contains an integer \( q \).
• The last line contains \( q \) integers representing the destination cities.

Output Format: Output a single line with ( q ) space-separated integers, where each integer is the shortest travel time from city 1 to the corresponding destination city. If a destination is unreachable, output -1 instead.

Note: All formulas are represented in LaTeX format.

inputFormat

The input is read from STDIN and is in the following format:

• The first line contains two integers \( n \) and \( m \) (number of cities and roads, respectively).
• Each of the next \( m \) lines contains three integers: \( u \), \( v \), and \( w \) representing a bidirectional road between cities \( u \) and \( v \) with travel time \( w \).
• The following line contains an integer \( q \), the number of destination cities.
• The last line contains \( q \) integers representing the destination cities.

outputFormat

Output a single line with ( q ) space-separated integers. The ( i^{th} ) integer should be the shortest travel time from city 1 to the ( i^{th} ) destination city as given in the input. If the city is unreachable, output -1 for that city.## sample

5 6
1 2 10
1 3 20
2 3 15
2 4 25
3 4 30
4 5 10
3
2 4 5

10 35 45