Minimum Flight Fare

You are given a set of direct flights between cities, where each flight is associated with a fare. Your task is to determine the minimum fare required to travel from city (A) to city (B). You may take one or more flights in sequence. If there is no possible sequence of flights between the two cities, output -1. If the source and destination are the same, the cost is 0. This problem can be modeled as a shortest path problem in a weighted directed graph and can be solved using Dijkstra's algorithm.

inputFormat

Input is given via standard input. The first line contains two integers (N) and (M) representing the number of cities and the number of flights, respectively. The following (M) lines each contain three integers (u), (v), and (w), indicating that there is a direct flight from city (u) to city (v) with a fare of (w). The last line contains two integers (A) and (B), the source and destination cities.

outputFormat

Output the minimum fare required to travel from city (A) to city (B) via a sequence of direct flights. If there is no possible route, print -1. In the case where (A = B), print 0.## sample

5 7
1 2 10
1 3 5
2 4 2
3 2 2
3 4 9
4 5 1
2 5 3
1 5

10