Shortest Path in an Undirected Graph

Given an undirected weighted graph with (N) nodes and (M) edges, your task is to compute the shortest path from a specified start node to a target node. Each edge is described by three integers (u), (v), and (w), where (w) represents the weight of the edge connecting nodes (u) and (v). The graph is undirected, meaning each edge can be traversed in both directions.

If a path exists, output the minimum total weight along any valid path. Otherwise, output -1 if no path exists.

The distance update in Dijkstra's algorithm can be modeled as: $$ d(v) = \min\big(d(v), d(u) + w(u,v)\big) $$

inputFormat

Input is read from standard input (stdin) and consists of multiple lines:
1. The first line contains two integers (N) and (M) representing the number of nodes and edges, respectively.
2. The following (M) lines each contain three integers (u), (v), and (w), indicating there is an edge between nodes (u) and (v) with weight (w).
3. The last line contains two integers: the start node and the target node.

outputFormat

Output a single integer to standard output (stdout): the length of the shortest path from the start node to the target node. If no valid path exists, output -1.## sample

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

7