Taco Dijkstra Shortest Path

You are given an undirected weighted graph with n nodes and m edges. Each edge connects two distinct nodes and has a positive weight. Your task is to determine the length of the shortest path from a given starting node to a destination node using Dijkstra's algorithm.

If there is no path between the starting node and the destination, output \(-1\).

The shortest path cost between two vertices \(u\) and \(v\) can be expressed as:

\(d(u,v)=\min_{\text{path }P:u\to v}\sum_{e\in P} w_e\)

Good luck!

inputFormat

The input is given via standard input (stdin) and consists of the following:

• The first line contains two integers \(n\) and \(m\) where \(n\) is the number of nodes and \(m\) is the number of edges.
• The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\) representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\).
• The last line contains two integers representing the start node and the destination node.

outputFormat

Output a single integer which is the length of the shortest path from the start node to the destination node. If there is no valid path, output \(-1\).

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

15