Minimum Cost Path in an Undirected Graph

You are given an undirected graph with (N) vertices and (M) edges. Each edge connects two vertices (x) and (y) with a positive weight (w). Your task is to compute the minimum cost to travel from vertex (A) to vertex (B). If there is no valid path, output (-1).

The input is provided via standard input and the result should be printed to standard output. Typically, this problem is solved using Dijkstra's algorithm for finding the shortest path in a weighted graph.

inputFormat

The first line contains two integers (N) and (M) — the number of vertices and edges respectively. The next (M) lines each contain three integers (x), (y) and (w), representing an undirected edge between vertices (x) and (y) with weight (w). The last line contains two integers (A) and (B) — the starting and destination vertices.

outputFormat

Print a single integer: the minimum cost to travel from vertex (A) to vertex (B). If no path exists, print (-1).## sample

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

6