Minimum Toll Fee

You are given a transportation network with N locations and M bidirectional roads. Each road connects two locations and has an associated toll fee. Your task is to compute the minimum total toll fee required to travel from Atlantis (location 1) to Elantia (location N).

If there is no path between these two locations, output -1.

Formally, given a graph \(G=(V,E)\) with \(N=|V|\) and a set of roads \(E\), where each road is represented as \((u,v,w)\) with \(w\) being the toll fee, determine the minimum sum of fees along any path from node 1 to node N.

Input Format: The first line contains two integers N and M. The next M lines each contain three integers \(u\), \(v\), and \(w\) indicating there is a road between locations \(u\) and \(v\) with toll fee \(w\).

Output Format: Print a single integer denoting the minimum total toll fee. If no path exists, print -1.

inputFormat

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

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

Where:

• N is the number of locations.
• M is the number of roads.
• Each of the following M lines contains three integers, u, v, and w, describing a road between locations u and v with toll fee w.

outputFormat

Output a single integer via standard output (stdout): the minimum total toll fee required to travel from Atlantis (node 1) to Elantia (node N). If there is no such path, output -1.

## sample

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

6