Shortest Path via Dijkstra's Algorithm

You are given a directed weighted graph and a start vertex. Your task is to compute the shortest path distances from the start vertex to every other vertex using Dijkstra's algorithm.

The input provides the number of vertices and edges, a list of vertex identifiers, the starting vertex, and then a list of edges. Each edge is given as a triple representing the source vertex, the destination vertex, and the weight. If a vertex is not reachable from the start vertex, consider its distance to be \(\infty\) (denoted as "INF" in the output).

Input Format:

• The first line contains two integers \(N\) and \(M\), where \(N\) is the number of vertices and \(M\) is the number of edges.
• The second line contains \(N\) distinct strings representing the vertex identifiers.
• The third line contains a string representing the starting vertex.
• The following \(M\) lines each contain two strings and an integer: the source vertex, the destination vertex, and the weight \(w\) of an edge.

Output Format:

• For each vertex (in the order given in the input), output a line in the format: vertex: distance. If the vertex is unreachable, output INF as its distance.

Note: You may assume that all edge weights are non-negative and that the graph does not contain negative cycles.

Example:

Input:
4 5
A B C D
A
A B 1
A C 4
B C 2
B D 5
C D 1
Output:
A: 0
B: 1
C: 3
D: 4

</p>

inputFormat

The input is read from stdin and has the following structure:

• The first line contains two integers \(N\) and \(M\), representing the number of vertices and edges respectively.
• The second line contains \(N\) space-separated strings denoting the vertices.
• The third line contains a single string \(S\), the starting vertex.
• Then follow \(M\) lines, each with two strings and an integer. Each line represents an edge: the source vertex, the destination vertex, and the weight (an integer).

outputFormat

The output is printed to stdout. For each vertex (in the same order as provided in the input), output a line in the format:

vertex: distance

If there is no path from the starting vertex to a vertex, output INF as its distance.

## sample

4 5
A B C D
A
A B 1
A C 4
B C 2
B D 5
C D 1

A: 0
B: 1
C: 3
D: 4

</p>