Minimum Traversal Cost

You are given a directed weighted graph representing a labyrinthine cave system with N rooms and M passages. Each passage from room u to room v has an associated traversal cost w. Your task is to find the minimum cost required to travel from room 1 to room N using the passages provided. If there is no valid path from room 1 to room N, your program should output -1.

This problem can be solved efficiently by employing Dijkstra's algorithm. The algorithm starts at room 1 and then iteratively relaxes the distances to all reachable rooms until it determines the shortest cost to reach room N.

Note: The input consists of multiple test cases. For each test case, you will be given the number of rooms, the number of passages, and the details of each passage.

inputFormat

The input is read from standard input. The first line contains an integer T representing the number of test cases. For each test case:

• The first line contains two integers N and M where N is the number of rooms and M is the number of passages.
• Each of the following M lines contains three integers u, v, and w representing a directed passage from room u to room v with a traversal cost w.

It is guaranteed that room 1 is the starting point and room N is the destination.

outputFormat

For each test case, output a single line containing the minimum traversal cost from room 1 to room N. If it is impossible to reach room N from room 1, output -1.## sample

2
4 4
1 2 5
2 3 10
1 3 15
3 4 5
3 3
1 2 4
1 3 6
2 3 1

20
5