포탈 게임

포탈 게임은 직선 위에서 진행되는 게임이다. 직선에는 $0$부터 $N-1$까지 번호가 붙은 $N$개의 칸이 있다. 게임의 목표는 $0$번 칸에서 출발해 $N-1$번 칸에 가능한 한 빠르게 도착하는 것이다.

이 게임에는 포탈이 총 $C$개 있으며, 포탈은 레드 포탈과 블루 포탈 두 종류가 있다. 각 칸에는 포탈의 시작 지점이 최대 $1$개 있을 수 있다. 시작 지점이 $a_i$번 칸인 포탈을 이용하면 끝 지점인 $b_i$번 칸으로 이동한다. 포탈은 시작 지점에서 끝 지점으로만 이동할 수 있으므로, 같은 포탈을 이용해 $b_i$번 칸에서 $a_i$번 칸으로 이동할 수는 없다.

$N-1$번 칸에 도착하기 전까지 각 칸의 종류에 따라 다음 행동을 할 수 있다.

• 포탈의 시작 지점이 없는 칸: 현재 위치인 $x$번 칸에서 $x + 1$번 칸으로 1초 후 이동한다.
• 레드 포탈의 시작 지점이 있는 칸: 시작 지점이 현재 위치 $x$번 칸인 레드 포탈을 이용해 끝 지점으로 0초 후 이동한다.
• 블루 포탈의 시작 지점이 있는 칸: 시작 지점이 현재 위치 $x$번 칸인 블루 포탈을 이용해 끝 지점으로 0초 후 이동하거나, $x$번 칸에서 $x + 1$번 칸으로 1초 후 이동한다.

첫 번째 줄에 칸의 개수 $N$과 포탈의 개수 $C$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 10^5$, $0 \leq C \leq N$)

두 번째 줄부터 $C$개의 줄에 걸쳐 포탈 정보가 한 줄에 하나씩 주어진다. 각 줄에는 정수 $t_i$, $a_i$, $b_i$가 공백으로 구분되어 주어진다. $t_i$는 $i$번째 포탈의 종류로, $t_i = 0$이면 레드 포탈, $t_i = 1$이면 블루 포탈이다. $a_i$와 $b_i$는 각각 $i$번째 포탈의 시작 지점과 끝 지점이 위치한 칸의 번호이다. ($t_i \in \{0, 1\}$, $0 \leq a_i, b_i \leq N-1$, $0 \leq i \leq C-1$)

모든 포탈의 시작 지점은 겹치지 않는다. 즉, $0 \leq i < j \leq C-1$이면 $a_i \neq a_j$이다.

첫 번째 줄에 $0$번 칸에서 출발해 $N-1$번 칸에 도착하는 데 걸리는 최소 시간을 출력한다.

어떤 방법으로 이동해도 $N-1$번 칸에 도착할 수 없으면 $-1$을 출력한다.