E. Raiffeisenbank Logistics
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

One of important business tasks for Raiffeisenbank is to improve the process of delivering cards, valuables, papers and so forth between banks, clients, pick-up points and other locations. You work in a pilot project that plans to revolutionize the world of delivery by using air drones and optimal routing algorithms.

You are now performing the very first tests at onsite training ground that consists of $$$n$$$ landing spots. There is a drone at spot $$$1$$$ and it needs to fly to spot $$$n$$$. Drone's remote control can run $$$m$$$ routing programs, the $$$i$$$-th program is able to move drone from spot $$$u_i$$$ to spot $$$v_i$$$ (if the drone is not at spot $$$u_i$$$, the program will do nothing), and it was written using $$$t_i$$$ version of your drone control library. As this is one of the first tests of your project you are not sure about compatibility of different versions of software, so each routing program you run (except for the very first) must have version of drone control library strictly greater, then the previous one.

After looking at the code of routing programs you found out that you can make little changes there. In particular, you can take any program $$$i$$$ and swap its starting and destination spots. So, if the $$$i$$$-th program moves drone from spot $$$u_i$$$ to spot $$$v_i$$$, after the changes it will move from from spot $$$v_i$$$ to spot $$$u_i$$$. Library version $$$t_i$$$ will remain unchanged.

Now you wonder, what is the minimum number of programs you need to change, so there will exist a sequence of programs $$$p_1, p_2, \ldots, p_k$$$ that being run in this order moves drone from spot $$$1$$$ to spot $$$n$$$, and $$$t_{p_1} \lt t_{p_2} \lt t_{p_3} \lt \ldots \lt t_{p_k}$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Then follow $$$t$$$ tests descriptions.

Each test description starts with two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 500\,000$$$, $$$1 \leq m \leq 500\,000$$$), the number of landing spots at the training ground and the number of routing programs respectively.

Then follow $$$m$$$ lines, the $$$i$$$-th of them describes the $$$i$$$-th program with three integers $$$u_i$$$, $$$v_i$$$ and $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$1 \leq t_i \leq 10^9$$$), meaning this program moves drone from spot $$$u_i$$$ to spot $$$v_i$$$ and uses $$$t_i$$$-th version of drone control library.

There can be multiple programs with the same version of software. There can be multiple programs connecting the same pair of spots (in each direction). There can be programs that move drone from some spot to itself.

It is guaranteed that sum of $$$n$$$ over all tests won't exceed $$$500\,000$$$. It is guaranteed that sum of $$$m$$$ over all tests won't exceed $$$500\,000$$$.

Output

If there is no way to change programs and move drone from spot $$$1$$$ to spot $$$n$$$ obeying condition that every next program you run must have greater version of drone control library, print -1 in the only line of the output.

Otherwise, print the minimum number of programs you need to change to achieve the goal.

Examples
Input
1
4 3
2 1 1
2 3 2
4 3 3
Output
2
Input
2
4 3
2 1 1
2 3 2
4 3 2
8 9
1 2 5
2 3 10
4 3 15
4 5 20
5 8 25
1 6 2
6 5 30
7 6 3
8 7 4
Output
-1
1