Portal Game

Portal Game is played on a straight line. The line has $N$ cells numbered from $0$ to $N-1$. The goal is to start at cell $0$ and reach cell $N-1$ as quickly as possible.

The game has $C$ portals in total, and each portal is either red or blue. Each cell can hold at most one portal entrance. Using the portal whose entrance is at cell $a_i$ moves you to its exit at cell $b_i$. Portals only work from entrance to exit, so you cannot use the same portal to go from $b_i$ back to $a_i$.

Before reaching cell $N-1$, you can take the following actions depending on the type of cell:

• A cell with no portal entrance: move from the current cell $x$ to cell $x + 1$, which takes 1 second.
• A cell with a red portal entrance: use the red portal to move to its exit in 0 seconds.
• A cell with a blue portal entrance: use the blue portal to move to its exit in 0 seconds, or move from cell $x$ to cell $x + 1$, which takes 1 second.

The first line contains the number of cells $N$ and the number of portals $C$, separated by a space. ($2 \leq N \leq 10^5$, $0 \leq C \leq N$)

Each of the next $C$ lines describes one portal. Each line contains three integers $t_i$, $a_i$, and $b_i$, separated by spaces. $t_i$ is the type of the $i$-th portal: $t_i = 0$ means red, and $t_i = 1$ means blue. $a_i$ and $b_i$ are the cell numbers of the entrance and exit of the $i$-th portal. ($t_i \in \{0, 1\}$, $0 \leq a_i, b_i \leq N-1$, $0 \leq i \leq C-1$)

No two portals share an entrance. That is, if $0 \leq i < j \leq C-1$, then $a_i \neq a_j$.

Print the minimum time needed to start at cell $0$ and reach cell $N-1$ on the first line.

If no sequence of moves reaches cell $N-1$, print $-1$.