Shortest Path in a Weighted Undirected Graph

You are given an undirected graph with n vertices and m weighted edges. Your task is to find the shortest distance from vertex 1 to vertex n using Dijkstra's algorithm. The graph can have multiple edges between the same pair of vertices, and the weights are positive integers. If there is no path from vertex 1 to vertex n, output -1.

Note: The answer should be computed exactly. Formally, given an undirected graph \(G=(V,E)\) with vertices numbered \(1,2,\dots,n\) and edges \(E\) where each edge \((u,v)\) has a weight \(w\), find the value:

[ d(1,n)=\min_{\text{paths }P\text{ from }1\text{ to }n}\sum_{e\in P}w(e), ]

and if no such path exists, output -1.

inputFormat

The input is read from standard input (stdin) in the following format:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where the first line contains two integers \(n\) (the number of vertices) and \(m\) (the number of edges). The next \(m\) lines each contain three integers \(u\), \(v\) and \(w\), representing an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer on standard output (stdout) which is the shortest distance from vertex 1 to vertex n. If there is no path, output -1.

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

7