Shortest Path in a Weighted Undirected Graph

You are given an undirected weighted graph with n nodes and m edges. The nodes are numbered from 1 to n. Each edge connects a pair of nodes and has a positive weight.

Your task is to determine the shortest path from node 1 to node n in terms of the sum of the weights of the edges along the path. If a path does not exist, output -1.

The length of a given path \(P\) is defined as \(\sum_{e \in P} w(e)\), where \(w(e)\) is the weight associated with edge \(e\).

inputFormat

The input is given via stdin and has the following format:

n m
u1 v1 w1
... 
um vm wm

Where:

• n is the number of nodes (2 ≤ n ≤ 10⁵).
• m is the number of edges (0 ≤ m ≤ 10⁵).
• Each of the following m lines contains three integers u, v and w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁹), representing an undirected edge between nodes u and v with weight w.

outputFormat

The output should be a single integer printed to stdout representing the length of the shortest path from node 1 to node n. If no such path exists, print -1.

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

10