영웅

바이테오티아에서 가장 이름난 영웅 바이테오테우스가 또 한 번 전투에서 승리했다. 선원들이 전리품을 배에 싣는 동안, 바이테오테우스는 선실에서 고향 섬 비타카로 돌아갈 길을 짠다. 쉬운 일이 아니다. 많은 신이 그의 인기를 시샘해 콧대를 꺾을 기회를 노린다. 다행히 그를 아끼는 신도 있다. 특히 여신 비테나가 그렇다. 어젯밤 바이테오테우스에게 꿈을 보내 앞으로 만날 위험을 알려 준 것도 비테나였다.

바이테오니아 해에는 섬이 $n$개 있고, 1번부터 $n$번까지 번호가 붙어 있다. 배는 지금 1번 섬에 있고, 목적지는 비타카, 즉 $n$번 섬이다. 어떤 두 섬은 일방통행 항로로 이어져 있으며, 항로에는 1번부터 $m$번까지 번호를 붙인다. $i$번 항로는 $a_i$번 섬에서 $b_i$번 섬으로 이어지고, 지나는 데 정확히 $d_i$일이 걸린다. 한 섬에서 출발하는 항로는 최대 10개다.

배가 $j$일 새벽에 $a_i$번 섬을 떠나 $i$번 항로로 나아가면 $j + d_i$일 새벽에 $b_i$번 섬에 닿는다. 배는 어느 섬에서든 원하는 만큼 오래 머물 수 있다. 다만 다음 섬에 닿기 전에는 정해진 항로를 벗어날 수 없고, 항로에 걸리는 기간보다 더 오래 바다에 있을 수도 없다. 바이테오테우스가 1번 섬을 떠날 수 있는 가장 이른 시점은 첫째 날 새벽이다.

비테나의 경고는 아주 구체적이었다. 신들이 준비한 함정 $p$개의 위치와 기간을 그대로 알려 주었다. 함정은 각각 한 섬에 놓여 있고 정해진 기간에만 작동한다. $i$번 함정은 $w_i$번 섬에 있고 $s_i$일부터 $k_i$일까지 작동한다. $k_i$일도 포함한다. 작동 중인 함정이 있는 섬에 배가 있으면 아무도 살아남지 못한다. 고향 비타카에는 함정이 없고, 1번 섬의 함정은 첫째 날에 하나도 작동하지 않는다.

배가 어떤 섬에 $x$일 새벽에 닿아 $y$일 새벽에 그 섬을 떠난다면, 배는 $x$일부터 $y$일까지 매일 그 섬에 있는 것으로 본다. 그 기간에 작동하는 함정이 그 섬에 하나라도 있으면 배는 살아남지 못한다.

바이테오테우스는 함정을 모두 피해 집으로 돌아가려 한다. 함정 때문에 항해가 얼마나 길어질지도 알고 싶다. 비타카까지 무사히 돌아가는 데 필요한 최소 일수를 구하라.

첫째 줄에 섬의 수 $n$과 항로의 수 $m$이 주어진다 ($2 \le n \le 100\,000$, $1 \le m \le 1\,000\,000$). 다음 $m$개 줄에 항로가 주어진다. $i$번째 줄에는 세 정수 $a_i$, $b_i$, $d_i$가 주어지며 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le d_i \le 10^9$), $i$번 항로가 $a_i$번 섬에서 $b_i$번 섬으로 이어지고 $d_i$일이 걸린다는 뜻이다. 모든 항로는 일방통행이다. 한 섬에서 출발하는 항로는 최대 10개다.

다음 줄에 함정의 수 $p$가 주어진다 ($0 \le p \le 100\,000$). 다음 $p$개 줄에 함정이 주어진다. $i$번째 줄에는 세 정수 $w_i$, $s_i$, $k_i$가 주어지며 ($1 \le w_i < n$, $1 \le s_i \le k_i \le 10^9$), $i$번 함정이 $w_i$번 섬에 있고 $s_i$일부터 $k_i$일까지 작동한다는 뜻이다. $w_i = 1$이면 $s_i > 1$이다.

함정을 모두 피하는 항로를 짤 수 없으면 첫째 줄에 NIE를 출력한다. 폴란드어로 아니오라는 뜻이다. 그렇지 않으면 항해에 필요한 최소 일수 $d$를 출력한다. 배는 $d + 1$일 새벽에 비타카에 닿는다.

첫 번째 예제에서 바이테오테우스는 첫째 날 새벽에 1번 섬을 떠나 넷째 날에 2번 섬에 닿는다. 거기서 하루를 기다린 뒤 3번 섬으로 떠나 여섯째 날에 도착하고, 곧바로 2번 섬으로 되돌아온다. 여덟째 날에 2번 섬을 떠나 4번 섬으로 향해 열째 날에 도착하며, 열한째 날에 비타카에 닿는다.