Logistic Routes

You are given a weighted directed graph and a sequence of vertices representing a route that must be followed. Your task is to calculate the total minimum travel time by summing the shortest path distances between each pair of consecutive vertices in the route. If any segment of the route is unreachable, output -1.

The shortest distance between two vertices u and v is defined as:

[ \text{Total Time} = \sum_{i=1}^{k-1} d(v_i,v_{i+1}) ]

where \(d(u,v)\) is the minimum travel time from vertex u to vertex v. Use Dijkstra's algorithm to compute the shortest paths.

inputFormat

The input contains one or more datasets. For each dataset:

• The first line contains two integers N and M, where N denotes the number of vertices and M the number of directed edges.
• The next M lines each contain three integers u, v, and t, representing an edge from vertex u to vertex v with weight t. If multiple edges exist between the same two vertices, consider the one with the minimum weight.
• The following line contains a sequence of integers representing the order of vertices to visit.

The input terminates with a single line containing 0.

outputFormat

For each dataset, output a single line containing the total minimum travel time. If any segment is unreachable, output -1 instead.

## sample

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

8
3

</p>