Shortest Travel Time

You are given an undirected weighted graph with n nodes and m edges. Each edge connects two nodes and has an associated positive travel time. Your task is to compute the shortest possible travel time from node 1 to node n.

In mathematical terms, given a graph \( G = (V, E) \) with \( |V| = n \) and edges \( E \) where each edge \( (u, v) \) has a weight \( w \), find the minimum value of:

[ \min_{\text{path } P: 1 \to n} \sum_{(u,v) \in P} w(u,v) ]

If there is no valid path from node 1 to node n, output -1.

The graph is bidirectional. Use efficient algorithms such as Dijkstra's algorithm to solve this problem.

inputFormat

The first line of input 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 nodes and m is the number of edges.
• Then follow m lines, each containing three integers u, v and w, indicating that there is an edge between node u and node v with travel time w.

Note: Nodes are numbered from 1 to n.

outputFormat

For each test case, output a single line containing the shortest travel time from node 1 to node n. If no path exists, output -1.

## sample

2
4 4
1 2 4
2 3 3
3 4 2
1 4 10
3 3
1 2 1
2 3 1
1 3 3

9
2

</p>