Minimum Path Finder

You are given an undirected graph consisting of N nodes and M edges. Each edge connecting two nodes has a positive integer weight. Your task is to find the minimum sum of weights along a simple path (i.e. no node is visited more than once) from node 1 to node N. If no such path exists, output -1.

The problem can be mathematically formulated as:

Find a path \( P = \{1 = v_1, v_2, \ldots, v_k = N\} \) such that the sum
\( S = \sum_{i=1}^{k-1} w(v_i, v_{i+1}) \) is minimized, where \( w(u,v) \) is the weight of the edge between nodes \( u \) and \( v \), and no node appears more than once in \( P \).

If there is no valid path, return -1.

inputFormat

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

N M
u1 v1 w1
u2 v2 w2
... 
uM vM wM

Here, the first line contains two integers, N (the number of nodes) and M (the number of edges). Each of the following M lines contains three integers u, v and w, representing an undirected edge connecting node u and node v with weight w.

outputFormat

Output a single integer to standard output (stdout): the minimum sum of weights along the path from node 1 to node N. If no such path exists, output -1.

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

16