Shortest Path in an Undirected Weighted Graph

You are given an undirected weighted 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 weight w. Your task is to compute the shortest path weight from a given start node to an end node using Dijkstra's algorithm.

If there is no valid path from the start node to the end node, output -1.

The shortest path weight \(d\) is defined as the minimum sum of weights along a path from the start node to the end node.

Input format: The first line contains four integers: \(n\) (number of nodes), \(m\) (number of edges), start and end. The following m lines each contain three integers: u, v, and w.

Output format: Output a single integer denoting the shortest path weight or -1 if no such path exists.

inputFormat

The input is read from stdin and has the following structure:

• The first line contains four space-separated integers: \(n\), \(m\), start, and end.
• The next \(m\) lines each contain three space-separated integers u, v, and w, representing an undirected edge from node u to node v with weight w.

outputFormat

The output is written to stdout and is a single integer representing the shortest path weight from the start node to the end node. If no such path exists, output -1.

4 4 0 3
0 1 1
1 2 2
0 2 4
2 3 1

4