Relay Race: Minimum Time Journey

In this problem, you are given a directed graph representing intersections and one-way roads. Each road has an associated travel time. Your task is to determine the minimum total time required to travel from a starting intersection (S) to an ending intersection (E). If no path exists, print (-1).

The graph has (N) intersections and (M) roads. Each road is described by a tuple ((u, v, t)), indicating a road from intersection (u) to intersection (v) that takes (t) time units. Efficient algorithms such as Dijkstra's algorithm may be used to find the solution.

inputFormat

The input is read from standard input (stdin).

The first line contains four integers separated by spaces: (N) (the number of intersections), (M) (the number of roads), (S) (the starting intersection), and (E) (the ending intersection).

Each of the next (M) lines contains three integers (u), (v), and (t), describing a one-way road from intersection (u) to intersection (v) with a travel time of (t).

outputFormat

Output a single integer to standard output (stdout): the minimum travel time from intersection (S) to intersection (E). If there is no valid path, print (-1).## sample

5 6 1 5
1 2 5
2 3 10
3 4 3
4 5 1
1 3 15
2 5 20

19