KOI 마을은 N개의 건물과 M개의 도로로 이루어져 있다.

건물에는 1부터 N까지의 번호가 붙어 있으며, 각 건물에는 창문이 있거나 없다.

1 \le i \le N인 각 i에 대해, i번 건물에 창문이 있으면 c_i = 1이고, 창문이 없으면 c_i = 0이다.

단, 1번 건물과 N번 건물에는 창문이 없어서, c_1 = c_N = 0이다.

도로에는 1부터 M까지의 번호가 붙어 있으며, 각 도로는 정확히 하나의 시작 건물과 하나의 도착 건물을 연결하는 일방통행 도로이다.

1 \le j \le M인 각 j에 대해, j번 도로는 x_j번 건물에서 시작하여 y_j번 건물에서 끝나며, 이 도로를 지나가는 데에는 정확히 t_j초가 걸린다.

일방통행 도로이기 땨문에 도로의 방향을 거슬러 이동하는 것(즉, y_j번 건물에서 x_j번 건물로 이동하는 것)은 불가능하다.

KOI 마을에서 한국이와 정올이는 "무궁화 꽃이 피었습니다." 놀이를 다음과 같이 변형한 게임을 진행하려 한다.

게임이 시작될 때, 정올이는 1번 건물에 있다.

정올이의 목표는 한국이의 시야에 한 번도 발각되지 않고 가능한 한 빠르게 N번 건물에 도착하는 것이다.

반면, 한국이의 목표는 정올이가 N번 건물에 도착하기 전에 그를 찾아내는 것이다.

한국이는 눈을 뜨고 있는 동안 KOI 마을 전체를 볼 수 있지만, 창문이 없는 건물 내부를 볼 수 없다.

즉, 한국이는 창문이 있는 건물 내부과 도로밖에 볼 수 없다.

한국이는 게임을 시작한 순간(0초)부터 다음 동작을 주기적으로 반복한다.

위의 과정을 수식으로 엄밀히 표현하면 다음과 같다.

현재 시각을 "게임을 시작한 순간부터 지나간 시간(초 단위)"으로 정의하자.
현재 시각을 t초라 할 때, t = k(a+b) + l(k는 음이 아닌 정수, l은 0 \le l \le a+b를 만족하는 실수)라 하자.
이때, 0 \le l \le a일 때는 한국이가 눈을 감고 있고, a < l < a+b일 때는 한국이가 눈을 뜨고 있다.
즉, 음이 아닌 정수 k에 대해, 한국이가 눈을 감고 있는 시간은 닫힌 구간 [k(a+b), k(a+b) + a]이고,
눈을 뜨고 있는 시간을 열린 구간(k(a+b) + a, (k+1)(a+b))이다.

정올이는 게임 시작 시간(0초)부터 언제든지 원할 때 이동을 시작할 수 있으며, 건물 내부에서는 창문 유뮤와 관계없이 원하는 만큼 자유롭게 대기 할 수 있다.

건물에서 도로로 나오거나 도로에서 건물 내부로 들어가는 데 소요되는 시간은 없다.

정올이가 어떤 도로를 통해 이동을 시작하면, 반드시 해당 도로의 소요 시간만큼 정확히 이동해야 하며,
이동 도중에는 도로 위에서 멈추거나 기다릴 수 없다. 이동이 끝나면 도로 끝의 건물이 도착한다.

정올이가 한국이에게 발각되는 기준은 다음과 같다.

한국이가 눈을 뜨고 있는 동안 정올이가 도로 위 또는 창문이 있는 건물 내부에 있으면, 즉시, 발각되어 게임이 곧바로 종료된다.
따라서 정올이는 한국이가 눈을 뜨고 있는 동안에는 반드시 창문이 없는 건물 내부에 있어야 한다.
한국이가 눈을 감고 있는 동안에는 정올이가 어디에 있든 절대 발각 되지 않는다.
정올이가 창문이 없는 건물에 진입한 시점이 정확히 한국이가 눈을 뜨기 시작한 순긴이나,
도로에 진입하여 이동을 시작하는 시점이 정확히 한국이가 눈을 감기 시작한 순간이라면 발간되지 않는다는 점에 유의하라.

이러한 조건 아래, 정올이가 한국이에게 단 한 번도 발각되지 않고 무사히 N번 건물에 도착하는 것이 가능한지 판단하고,
만약 가능하다면 정올이가 N번 건물에 도착할 수 있는 가장 빠른 시간을 초 단위로 계산하는 프로그램을 작성하라.

주어지는 모든 수는 정수이다.

3 \le N \le 2,000
3 \le M \le 4,000
1 \le j \le M인 각 j에 대해 1 \le x_j, y_j \le N, x_j \ne y_j, 1 \le t_j <= 100,000
1 \le j < k \le M인 각 j, k에 대해 (x_j, y_j) \ne (x_k, y_k). 즉, 두 도로의 시작 건물과 도착 건물이 모두 서로 같은 경우는 없다.
2 \le i \le N-1인 각 j에 대해 c_i \in \{0, 1\}
c_1 = c_N = 0이다. 즉, 1번 건물과 N번 건물에는 창문이 없다.
1 \le a,b \le 10^9

무궁화 꽃이 피었습니다 timer 2s memory 1024MB

무궁화 꽃이 피었습니다 2s 1024MB