Shortest Path with Dijkstra's Algorithm

You are given an undirected weighted graph with n cities (vertices) and m roads (edges). Each road connects two different cities and has an associated positive weight. Your task is to compute the shortest path from a starting city s to a target city t using Dijkstra's algorithm.

If there is no possible path from s to t, output -1. Note that the cost of a path is defined as:

\(\text{Cost} = \sum_{i=1}^{k} w_i\)

where \(w_i\) represents the weight of the i-th edge along the path. When s is equal to t, the shortest path length is 0.

inputFormat

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

The first line contains two space-separated integers (n) and (m), representing the number of cities and the number of roads respectively.

Each of the next (m) lines contains three space-separated integers (u), (v), and (w), denoting an undirected edge between cities (u) and (v) with a weight (w).

The last line contains two integers (s) and (t), representing the starting and target cities respectively.

outputFormat

Output a single integer to the standard output (stdout) representing the length of the shortest path from city (s) to city (t). If there is no such path, output -1.## sample

5 6
1 2 2
1 3 1
2 3 4
2 4 7
3 5 3
4 5 1
1 5

4