Shortest Path in a Directed Graph

Given a directed graph with n cities (nodes) and m roads (edges), find the minimum travel time from the starting city to the destination city. Each road is described by three integers: the starting city u, the ending city v, and the travel time w.

You need to compute the shortest path from city s to city d using Dijkstra's algorithm. If there is no available path, output -1.

The relationship used by Dijkstra's algorithm can be represented as:

$$\text{distance}[v] = \min(\text{distance}[v],\, \text{distance}[u] + w) $$

where \(u\) is a node connected to \(v\) with an edge weight \(w\).

inputFormat

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

 n m s d
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm

Here, the first line contains four integers:

• n: the number of cities,
• m: the number of roads,
• s: the starting city,
• d: the destination city.

Each of the next m lines contains three integers u, v, and w representing a road from city u to city v with a travel time of w.

outputFormat

Output a single integer to standard output (stdout): the minimum travel time from city s to city d. If no such path exists, output -1.

## sample

4 4 1 3
1 2 5
2 3 10
1 3 15
3 4 5

15