Minimum Artifact Retrieval Path

In an ancient labyrinth filled with mysterious rooms and hidden passages, a team of ninjas is tasked with retrieving a powerful artifact. The artifact is located in room N, and the ninjas start from room 1. Each passage between rooms has an associated travel cost. Your mission is to compute the shortest travel distance from room 1 to room N. If no valid path exists, return -1.

The passages are one-way and are described by triplets \( (u, v, w) \), representing a passage from room \( u \) to room \( v \) with a travel cost of \( w \). You are required to use an efficient algorithm (such as Dijkstra's algorithm) to solve this problem, even for large mazes.

inputFormat

The first line contains two integers \( N \) and \( M \), the number of rooms and the number of passages, respectively.

Each of the next \( M \) lines contains three integers \( u \), \( v \), and \( w \), representing a directed passage from room \( u \) to room \( v \) with weight \( w \).

outputFormat

Output a single integer: the length of the shortest path from room 1 to room N. If there is no valid path, output -1.

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

6