Minimum Travel Cost

You are given a graph of n cities connected by m bidirectional routes. Each route connects two distinct cities and has an associated travel cost.

Your task is to compute the minimum travel cost from a given starting city to a destination city. If there is no valid path, output -1.

You are expected to solve the problem using Dijkstra's algorithm. Recall that the updating rule in Dijkstra's algorithm can be mathematically expressed as:

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

where \(d[v]\) represents the minimum known distance to vertex \(v\) and \(w(u,v)\) is the weight of the edge from \(u\) to \(v\).

inputFormat

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

 n m
 start end
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm

Here, the first line contains two integers n (number of cities) and m (number of routes). The second line contains two integers, the starting city start and the destination city end. Each of the following m lines contains three integers u, v and w representing a bidirectional route connecting cities u and v with travel cost w.

outputFormat

Output via standard output (stdout) a single integer representing the minimum travel cost from the starting city to the destination city. If no valid path exists, output -1.

## sample

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

8