Minimum Travel Time

You are given a network of n teleportation points and m one-way paths. Each path is represented as a tuple (u, v, t) indicating that one can travel from teleportation point u to point v in t units of time. Given a starting point s and a destination point d, your task is to compute the minimum travel time required to reach d from s. If there is no available path, output -1.

The problem can be modelled as finding the shortest path in a directed weighted graph where all the edge weights are non-negative. A well-known algorithm to solve this problem is Dijkstra's algorithm. In this problem, if s equals d, the travel time is 0.

The answer should be output to standard output (stdout) in the form of an integer. Use the LaTeX formatting for any formulas. For instance, the distance can be represented as \(d(s, d)\) and the relaxation step as \(\min\{d(u) + t, d(v)\}\).

inputFormat

The input is read from standard input (stdin) and is structured as follows:

n m
u1 v1 t1
u2 v2 t2
... 
um vm tm
s d

Here, the first line contains two integers, \(n\) (the number of teleportation points) and \(m\) (the number of one-way paths). The next \(m\) lines each contain three integers, representing a path from u to v with travel time t. The final line contains two integers, s (the starting point) and d (the destination point).

outputFormat

Output a single integer which is the minimum travel time from s to d. If d is not reachable from s, output -1.

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

9