Shortest Travel Time

You are given a directed graph representing a city with n intersections and m roads. Each road connects two intersections and has an associated travel time. Your task is to compute the shortest travel time from a given start intersection s to an end intersection t. If there is no possible path from s to t, output -1.

The problem can be formalized as follows. Given a directed graph \(G=(V,E)\) with \(|V| = n\) and \(|E| = m\), for each edge \((u, v)\) there is an associated travel time \(c\). Find the minimum total travel time from \(s\) to \(t\), i.e., the minimum value of \(\sum_{(u, v) \in P} c_{uv}\) over all paths \(P\) from \(s\) to \(t\). If no such path exists, the answer is \(-1\).

Note: Use Dijkstra's algorithm for an efficient solution.

inputFormat

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

1. The first line contains four integers n, m, s, and t, where n is the number of intersections, m is the number of roads, s is the starting intersection, and t is the destination intersection.
2. The following m lines each contain three integers u, v, and c representing a road from intersection u to intersection v with travel time c.

outputFormat

Print a single integer representing the shortest travel time from s to t. If there is no path from s to t, output -1.

5 6 1 5
1 2 4
1 3 2
2 3 5
3 4 1
2 5 10
4 5 3

6