In a country, there are N cities numbered from 1 to N.

There are M trains in the country which are used by people to move from one city to another. Each train starts from city L_i and ends at city R_i and the cost of taking the train is W_i. One can travel between any two cities (from smaller index to larger one) that lie between L_i and R_i ( both inclusive) with the cost of W_i.

More formally people can travel from city u to v $(L_i\le u<v\le R_i)$ at the cost of W_i $(1\le i\le M)$.

Task

Determine the minimum cost required to travel from city 1 to city N. If the city N is not reachable from city 1 then print -1.

Notes

• Assume 1-based indexing
• Trains are given in form of array A of size M*3, denoting the starting city, ending city, and the cost

Example

Assumptions

• N = 5
• M = 2
• A = [ [1, 3, 5], [2, 5, 10] ]

Approach

• First, take the first train from city 1 and reach city 2 at a cost of 5.
• Then take the second train from city 2 to city 5 at a cost of 10.
• Thus the total cost to travel from city 1 to 5 is 5+10=15. 

Hence, the answer is 15.

Function description

Complete the function solve provided in the editor. This function takes the following 3 parameters and returns the minimum cost required to travel from city 1 to city N:

• N: Represents the number of cities
• M: Represents the number of trains
• A: Represents array in which A[i][0], A[i][1], and A[i][2] represent the city at which i^th train starts, the city at which i^th train ends, and the cost of taking the train respectively

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • The first line contains 2 integer N and M represents the number of cities and the number of trains.
  • The Next M line contains 3 space-separated integers that represent the city at which i^th train starts, the city at which i^th train ends, and the cost of taking the train respectively.

Output format

For each test case in a new line, print the minimum cost required to travel from city 1 to city N. If the city N is not reachable from city 1 then print -1.

Constraints

$1 \le T \le 10\\ 2 \le N \le 10^{5}\\ 1 \le M \le 10^{5}\\1 \le L_i<R_i \le N\\1\le W_i \le 10^{9}$

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.