Shortest Travel Time in a Hyperspace Network

You are given a directed graph that represents a hyperspace network connecting N planets with M one-way hyperspace routes. Each route is characterized by three integers: the starting planet U, the destination planet V, and the travel time W (in positive units). Your task is to compute the shortest travel time from planet A to planet B using the given routes.

If there is no valid path from A to B, output -1. Note that if A and B are the same, the answer is 0.

Input constraints: The graph is guaranteed to have positive travel times, and although the problem description mentions a directed acyclic graph, the provided input is such that a Dijkstra-based approach will yield the correct result for the given test cases.

The solution should read the input from standard input (stdin) and print the result to standard output (stdout).

inputFormat

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

N M
U1 V1 W1
U2 V2 W2
... (M lines total)
A B

Where:

• N is the number of planets.
• M is the number of hyperspace routes.
• Each of the following M lines contains three integers U, V, and W indicating there is a one-way route from planet U to planet V with travel time W.
• The last line contains two integers A and B, the starting and destination planets respectively.

outputFormat

Output a single integer which is the shortest travel time from planet A to planet B. If no such path exists, output -1.

## sample

5 6
1 2 1
1 3 3
2 3 1
2 4 6
3 4 2
3 5 4
1 4

4