Shortest Travel Time

You are given a network of N towns connected by R roads. Each road connects two different towns and has a travel time associated with it. Your task is to determine the minimum travel time from a starting town S to a destination town T using the available roads. If there is no path from S to T, output -1.

The road network can be modeled as an undirected graph, where each town is a node and each road is an edge. The problem is equivalent to finding the shortest path in a weighted undirected graph. One common approach is to use Dijkstra's algorithm. In mathematical terms, if we denote the distance from S to a town u as \(d(u)\), then for each edge \((u,v)\) with weight \(w\) the following relaxation is performed:

[ d(v) = \min{d(v),; d(u) + w} ]

Good luck!

inputFormat

The input is given from standard input (stdin) and has the following format:

N M S T
u1 v1 w1
u2 v2 w2
... 
[uM vM wM]

Where:

• N is the number of towns.
• M is the number of roads.
• S is the starting town.
• T is the destination town.
• Each of the next M lines contains three integers u, v, and w representing a road between towns u and v with travel time w.

outputFormat

Output the minimum travel time from town S to town T to standard output (stdout). If there is no valid path, output -1.

## sample

5 7 1 4
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
4 5 9

20