Shortest Path in an Undirected Weighted Graph

Given an undirected weighted graph with (n) vertices and (m) edges, your task is to compute the shortest distance from vertex 1 to vertex (n) using Dijkstra's algorithm. If there is no valid path from vertex 1 to vertex (n), output (-1). Note that when (n = 1), the distance is defined as (0).

Graph edges are provided in the format: each edge connects two vertices (u) and (v) with an associated weight (w). Your solution should read from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input is given via standard input. The first line contains two integers (n) and (m), representing the number of vertices and edges respectively. The next (m) lines each contain three integers (u), (v) and (w) representing an undirected edge between vertex (u) and vertex (v) with weight (w).

outputFormat

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

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

4