Shortest Path in an Undirected Graph

You are given an undirected weighted graph. The graph consists of n nodes numbered from 1 to n and m edges. Each edge connects two nodes and has a non-negative weight.

Your task is to determine the minimum total weight of a path from node 1 to node n. If no such path exists, output -1 instead.

The mathematical formulation of the problem can be stated as follows:

Given a graph \( G = (V, E) \) where \( |V| = n \) and \( |E| = m \), find the minimum value of \( \sum_{(u,v) \in P} w(u,v) \) for any path \( P \) from node \(1\) to node \(n\). If no path exists, report \( -1 \).

inputFormat

The first line of input contains two space-separated integers, n and m, representing the number of nodes and the number of edges respectively.

The following m lines each contain three space-separated integers, u, v, and w, indicating that there is an undirected edge between nodes u and v with weight w.

Note: When n is 1 and m is 0, the output should be 0.

outputFormat

Output a single integer: the minimum weight of a path from node 1 to node n. If such a path does not exist, output -1.

4 4
1 2 5
2 3 10
1 3 20
3 4 1

16