Shortest Path in a Weighted Graph

Given a weighted graph represented as an adjacency list, your task is to find the shortest path between two specified nodes. The graph is undirected and each edge carries an integer weight.

If a path exists, output the total weight of the shortest path; otherwise, output \(-1\). Note that if the source and destination are the same, the answer is \(0\).

You are expected to use a standard algorithm such as Dijkstra's algorithm to solve the problem.

The problem can be formally stated as: Given a graph \(G = (V, E)\) with weights \(w: E \to \mathbb{N}\), and two vertices \(s\) and \(t\) from \(V\), find the minimum distance \(d(s,t)\). If no such path exists, output \(-1\).

inputFormat

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

N M
node1 node2 ... nodeN
u1 v1 w1
u2 v2 w2
... (M edges)
start_node end_node

Where:

• N is the number of nodes.
• M is the number of edges.
• The second line lists the names of the nodes separated by spaces.
• Each of the next M lines contains two node names and an integer weight representing an undirected edge.
• The last line contains the start and end node names.

outputFormat

Output a single integer to the standard output: the length of the shortest path from the start node to the end node. If there is no path between them, output \(-1\).

## sample

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

4