32188번 - Portal Game

문제

포탈 게임은 직선 위에서 진행되는 게임이다. 직선에는 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ドル$초 후 이동한다.

0ドル$번 칸에서 출발해 $N - 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$번째 포탈의 시작 지점이 위치한 칸의 번호, $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$을 출력한다.

제한

힌트