Find the Treasure

You are given a directed graph representing a series of caves connected by one-way tunnels. Each tunnel has an associated travel cost. The graph consists of N nodes (caves) numbered from 1 to N, with cave 1 always being the entrance and cave N containing the treasure. Your task is to determine the minimum travel cost needed to travel from the entrance to the treasure cave. If there is no possible path from cave 1 to cave N, output -1.

The travel costs are non-negative. It is guaranteed that each test case describes a valid cave system. Use Dijkstra's algorithm or another efficient shortest path algorithm to solve the problem.

The formula for updating the cost is given by:

\(d[v] = \min(d[v],\; d[u] + w)\)

where \(d[u]\) is the minimum cost to reach cave \(u\), and \(w\) is the travel cost from cave \(u\) to cave \(v\).

inputFormat

The input is read from standard input (stdin). The first line contains an integer T, the number of test cases. Each test case starts with a line containing two integers N and M, where N is the number of caves and M is the number of tunnels. The following M lines each contain three integers u, v, and w, indicating a one-way tunnel from cave u to cave v with a travel cost w.

outputFormat

For each test case, output a single integer on a new line representing the minimum travel cost to reach cave N from cave 1. If it is impossible to reach cave N, output -1.## sample

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

5
4