Minimum Package Delivery Time

In this problem, you are given a warehouse with n stations and m conveyor belts connecting the stations. Each conveyor belt connects two stations and has an associated travel time. Given a starting station s and a destination station t, your task is to compute the minimum time required to move a package from s to t. If no valid path exists, print -1.

We can model the warehouse as an undirected weighted graph (G=(V,E)) where each edge (e \in E) has a weight representing the time. The problem requires you to compute the shortest path from vertex (s) to vertex (t).

inputFormat

The input is given from standard input (stdin). The first line contains two integers (n) and (m) representing the number of stations and the number of conveyor belts respectively. The next (m) lines each contain three integers (u), (v), and (w), indicating that a conveyor belt exists between station (u) and station (v) with travel time (w). The last line contains two integers (s) and (t), representing the starting and destination stations.

outputFormat

Print the minimum delivery time to move the package from station (s) to station (t). If there is no possible path, print -1.## sample

5 6
1 2 5
2 3 2
1 3 9
3 4 3
2 4 7
4 5 1
1 5

11