Minimum Travel Time

You are given a list of flights between airports. Each flight is represented by three values: the source airport, the destination airport, and the travel time between these two airports. Your task is to compute the minimum travel time from a starting airport \(s\) to a target airport \(t\). If there is no possible route, output \(-1\).

The flight information can be modeled as a weighted directed graph where the nodes represent airports and the edges represent flights. The travel time along each flight is analogous to the weight of the edge. A common approach to solve this problem is to use Dijkstra's algorithm which computes the shortest path in a graph with non-negative edge weights.

Input Format: The first number represents the total number of flights. Each of the following lines describes a flight with a source airport, a destination airport, and an integer travel time. The final line contains two strings representing the starting airport and the destination airport.

Output Format: Output a single integer value representing the minimum travel time from the starting airport to the destination airport. If there is no valid route, output \(-1\).

inputFormat

The input is read from stdin and is given as follows:

1. An integer \(n\) indicating the number of flights.
2. \(n\) lines, each containing two strings and an integer: source destination time.
3. A final line with two strings: start end.

All values are space-separated.

outputFormat

The output is written to stdout and consists of a single integer: the minimum travel time from the start airport to the end airport. If no valid route exists, output -1.

## sample

4
A B 2
B C 3
A C 6
C D 1
A D

6

</p>