Minimum Cost to Travel

You are given an undirected weighted graph with N nodes and M edges. Each edge connects two nodes and has an associated weight. The task is to compute the minimum cost required to travel from node 1 to node N. If there is no valid path from node 1 to node N, output -1.

The cost of a path is defined as the sum of the weights of the edges in the path. Mathematically, if a path consists of edges with weights \(w_1, w_2, \dots, w_k\), then the total cost is given by

[ \text{Cost} = \sum_{i=1}^{k} w_i ]

You are recommended to solve this problem using Dijkstra's algorithm since all edge weights are non-negative.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers, N (the number of nodes) and M (the number of edges).
• The next M lines each contain three integers u, v, and w indicating that there is an undirected edge between node u and node v with weight w.

outputFormat

Output a single integer to stdout: the minimum cost to travel from node 1 to node N. If there is no such path, output -1.

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

3