Shortest Delivery Route

You are given the task of determining the minimum time required to deliver a package from one city to another using the company’s road network. The network is represented as an undirected graph, where each vertex represents a city and each edge represents a direct route between two cities with an associated travel time.

The problem can be formulated as follows. Given a graph \(G=(V,E)\) where each edge \(e \in E\) has a weight \(w(e)\), and given a starting city and a destination city, find the shortest path (in terms of travel time) between the two cities. If no such path exists, output NO PATH.

The input consists of multiple test cases. Each test case begins with a line containing two integers: the number of cities and the number of routes. This is followed by several lines describing each route and finally a line containing the start and destination cities. The test cases end with a line containing a single 0.

Implement a solution using Dijkstra's algorithm.

inputFormat

The input is given via standard input (stdin). It consists of multiple test cases. Each test case is structured as follows:

• The first line contains two integers: num_cities and num_routes.
• The next num_routes lines each contain two city names and an integer time representing a direct route: "City1 City2 Time".
• Then a line with two strings indicating the starting city and the destination city.
• The sequence of test cases ends with a line that contains a single 0.

outputFormat

For each test case, output the minimum travel time required to go from the starting city to the destination city. If there is no valid route, output NO PATH. Each result should be printed on a new line to standard output (stdout).

4 3
A B 10
B C 20
C D 30
A D
0

60