Shortest Path in a Bidirectional Attraction Network

You are given a network of attractions connected by bidirectional paths. Each path has an associated travel time. Your task is to find the minimum total travel time required to get from Attraction 1 to Attraction N. If there is no possible route from Attraction 1 to Attraction N, output -1.

The problem can be mathematically described as follows:

Find the minimum distance d from node 1 to node N in an undirected weighted graph, i.e., \[ d = \min_{\text{path } 1 \to N} \sum_{(u,v) \in \text{path}} w(u,v), \] with the condition that if no path exists, then d = -1.

Note: The graph has N attractions and M paths. Each path is defined by two endpoints and a travel time.

inputFormat

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

• The first line contains two integers N and M, which represent the number of attractions and paths respectively.
• The next M lines each contain three integers u, v, and w, indicating that there is a bidirectional path between attractions u and v with a travel time of w.

You can assume that the input values are separated by spaces and/or newline characters.

outputFormat

Output one integer to stdout, which is the minimum travel time required to reach Attraction N from Attraction 1. If Attraction N cannot be reached from Attraction 1, output -1.

4 4
1 2 4
2 4 6
1 3 2
3 4 8

10