Shortest Path Using Dijkstra's Algorithm

You are given an undirected graph with N nodes and M edges. Each edge is described by three integers u, v, and w, representing an edge between nodes u and v with non-negative weight w. Additionally, you are provided with two integers S and T representing the start and target nodes respectively.

Your task is to compute the shortest path from S to T using Dijkstra's algorithm. If no valid path exists, output -1. In cases where the start equals the target, the shortest distance is 0.

Recall that Dijkstra's algorithm uses the following idea: initialize distances using
$\mathrm{dist}[i] = \infty$ for all nodes, except $\mathrm{dist}[S]=0$, and then iteratively relax the distances by considering the shortest unvisited node. Here, $\infty$ denotes a value that is larger than any possible path length.

inputFormat

The input is given in the following format:

• The first line contains two integers N and M, representing the number of nodes and edges respectively.
• The next M lines each contain three integers u, v, and w, describing an edge between nodes u and v with weight w.
• The last line contains two integers S and T, representing the starting and target nodes.

All input is read from standard input (stdin).

outputFormat

Output a single integer: the length of the shortest path from S to T. If no path exists, output -1. The result should be printed to standard output (stdout).

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

12