Minimum Difficulty Level

You are given a game map with n checkpoints and m bidirectional pathways. Each pathway is characterized by three integers: u, v and w, representing a connection between checkpoints u and v with difficulty level w.

Your task is to determine the minimum total difficulty required to travel from checkpoint 1 (the spawn point) to checkpoint n (the goal). If there is no valid path, output -1.

This problem can be efficiently solved using Dijkstra's algorithm.

inputFormat

The first line contains two integers n and m separated by a space, indicating the number of checkpoints and the number of pathways, respectively.

Each of the following m lines contains three integers u, v and w, representing a bidirectional pathway connecting checkpoints u and v with difficulty level w.

outputFormat

Output a single integer representing the minimum total difficulty from checkpoint 1 to checkpoint n. If it's impossible to reach the goal, output -1.

## sample

5 7
1 2 10
1 3 5
2 4 2
2 5 2
3 4 9
3 5 1
4 5 3

6

</p>