무능한 배달 오크

이센가드의 마법사 사루만은 몇 가지 마법의 도움을 받아 $n$ 개의 탑 사이에 수송 체계를 만들었다. 정확히 말하면, 두 탑을 잇는 단방향 통로 $m$ 개를 만들었다. 각 통로 $i$에는 오크가 그 통로를 지나는 데 걸리는 시간(초)을 나타내는 수 $t\_i$가 붙어 있다. 즉, 사루만의 수송 체계는 방향 가중치 그래프로 표현할 수 있다.

12월 15일, 가운데 탑인 오르상크에 있던 사루만에게 팔란티르를 통해 사우론의 전갈이 도착한다. 귀한 선물이 이미 이센가드 입구 탑 근처까지 와 있다는 내용이다. 그래서 사루만은 수비대에게 오크 한 명을 골라 입구 탑에서 오르상크까지 가장 짧은 경로로 선물을 전달하라고 지시해야 한다.

그런데 오크들은 그다지 영리하지 않다. 수송 체계의 통로를 따라 짐을 끌고 갈 수는 있고, (원칙적으로는) 오르상크가 어디인지도 안다. 그러나 최단 경로라는 개념은 거의 이해하지 못한다. 모두의 수고를 덜기 위해 사루만은 일부 탑에 "TO ORTHANC - THIS WAY"라고 적힌 커다란 깜빡이 표지판을 달고, 그 탑에서 나가는 통로 중 하나를 가리키게 한다. 사루만은 오크들이 최대한 빨리 도착하기를 바라므로, 표지판은 오르상크까지의 최단 경로 중 하나에 놓인 통로만 가리킬 수 있다. 형식적으로 말하면, 탑 $u$의 표지판이 통로 $\vec{a} = \overrightarrow{uv}$를 가리킬 수 있는 조건은 $\mathop{\overrightarrow{\mathrm{dist}}}(v, O) < +\infty$이고 $\mathop{\overrightarrow{\mathrm{dist}}}(u, O) = t\_{\vec{a}} + \mathop{\overrightarrow{\mathrm{dist}}}(v, O)$가 성립하는 것이다. 여기서 $\mathop{\overrightarrow{\mathrm{dist}}}(x, y)$는 탑 $x$에서 탑 $y$로 가는 데 걸리는 최소 시간이며(방향 경로가 없으면 $+\infty$), $O$는 오르상크 탑, $u$와 $v$는 통로 $\vec a$의 출발 탑과 도착 탑이다. 사루만은 오르상크에는 표지판을 달지 않고, 오르상크에 도달할 수 없는 탑에도 달지 않는다. 그 밖의 모든 탑에는 표지판을 정확히 하나씩 단다.

그래도 완벽하게 작동하지는 않는다. 오르상크로 이동하는 동안 오크가 (오르상크를 제외한) 어떤 탑 근처에 올 때마다, 오크는 표지판이 붙은 통로를 고르거나, 사루만이 부르는 이른바 "어슬렁거리기"를 할 수 있다. 어슬렁거리기는 오크가 나가는 통로를 완전히 무작위로 고르는 것이다. 어떤 오크든 오르상크로 가라는 명령을 받았을 때, 이동 중 어슬렁거리기를 $d$번보다 많이 하지 않는 정수 $d$가 존재한다. 이 값을 그 오크의 "무능도"라고 부르기로 하자.

또 어떤 순간에는 오크가 오르상크로 가는 방향 경로가 없는 탑 근처에 놓일 수도 있다. 이런 불운한 상황에서는 가장 무능한 오크라도 그 탑에서 표지판을 찾지 못하고, 임무가 실패했음을 알아차린 뒤 즉시 멈추어 구조 작업을 기다린다.

사루만은 부하들이 그리 뛰어난 머리를 가지지 못했다는 것을 알고 있으므로, 선물이 빨리 도착하기를 기대하지는 않는다. 다만 최소한 성공하기를 원한다. 따라서 이 임무에 가능한 한 유능한 오크를 배정하는 것이 합리적이다. 하지만 유능한 오크는 드물고, 현재 하고 있는 일에서 빼내면 그 일이 크게 흐트러질 수 있다. 그러므로 이센가드 수송 체계에 대한 설명이 주어졌을 때, 사루만이 표지판을 적절히 배치하여, 무능도가 $d$인 오크를 입구 탑에서 선물 배달에 배정하면 반드시 오르상크에 도착하게 되는 최대의 $d$를 구하라.

첫째 줄에 탑의 개수 $n$과 단방향 통로의 개수 $m$이 주어진다($2 \le n \le 4 \cdot 10^5$; $0 \le m \le 4 \cdot 10^5$). 이어지는 $m$개의 줄에 통로의 정보가 주어진다. 각 줄에는 세 정수 $u\_i$, $v\_i$, $t\_i$가 들어 있으며, 각각 통로의 출발 탑 번호, 도착 탑 번호, 짐을 든 오크가 그 통로를 지나는 데 걸리는 초 단위 시간이다($1 \le u\_i, v\_i \le n$; $1 \le t\_i \le 10^6$). 같은 두 탑을 잇는 통로가 여러 개 있을 수 있으며, 방향은 어느 쪽이든 가능하다. 자기 자신으로 돌아오는 통로도 있을 수 있다. 즉, 자기 루프, 다중 통로, 양방향 통로 쌍이 모두 허용된다.

입구 탑의 번호는 1이고, 오르상크의 번호는 $n$이다.

정수 $d$ 하나를 출력하라. 이는 배달을 반드시 완료할 수 있는 오크의 무능도 최댓값이다. 어떤 무능도에서든 가능하다면 탑의 개수 $n$을 출력하라. 반대로 어떤 무능도에서도 불가능하다면 $-1$을 출력하라.