34120번 - 무궁화 꽃이 피었습니다 서브태스크

문제

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

건물에는 1ドル$부터 $N$까지의 번호가 붙어 있으며, 각 건물에는 창문이 있거나 없다. 1ドル ≤ i ≤ N$인 각 $i$에 대해, $i$번 건물에 창문이 있으면 $c_i = 1$이고, 창문이 없으면 $c_i = 0$이다. 단, 1ドル$번 건물과 $N$번 건물에는 창문이 없어서, $c_1 = c_N = 0$이다.

도로에는 1ドル$부터 $M$까지의 번호가 붙어 있으며, 각 도로는 정확히 하나의 시작 건물과 하나의 도착 건물을 연결하는 일방통행 도로이다. 1ドル ≤ j ≤ M$인 각 $j$에 대해, $j$번 도로는 $x_j$번 건물에서 시작하여 $y_j$번 건물에서 끝나며, 이 도로를 지나가는 데에는 정확히 $t_j$초가 걸린다. 일방통행 도로이기 때문에 도로의 방향을 거슬러 이동하는 것(즉, $y_j$번 건물에서 $x_j$번 건물로 이동하는 것)은 불가능하다.

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

게임이 시작될 때, 정올이는 1ドル$번 건물에 있다. 정올이의 목표는 한국이의 시야에 한 번도 발각되지 않고 가능한 한 빠르게 $N$번 건물에 도착하는 것이다. 반면, 한국이의 목표는 정올이가 $N$번 건물에 도착하기 전에 그를 찾아내는 것이다.

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

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

• 먼저 정확히 $a$초 동안 눈을 감는다. 곧이어 정확히 $b$초 동안 눈을 뜨고 마을을 감시한다.
• 다시 $a$초 동안 눈을 감는다. 곧이어 정확히 $b$초 동안 눈을 뜨고 마을을 감시한다.
• 이 과정을 끊임없이 반복한다.

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

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

정올이는 게임 시작 시점(0ドル$초)부터 언제든지 원할 때 이동을 시작할 수 있으며, 건물 내부에서는 창문 유무와 관계없이 원하는 만큼 자유롭게 대기할 수 있다. 건물에서 도로로 나오거나 도로에서 건물 내부로 들어가는 데 소요되는 시간은 없다. 정올이가 어떤 도로를 통해 이동을 시작하면, 반드시 해당 도로의 소요 시간만큼 정확히 이동해야 하며, 이동 도중에는 도로 위에서 멈추거나 기다릴 수 없다. 이동이 끝나면 도로 끝의 건물에 도착한다.

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

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

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

입력

첫 번째 줄에 두 정수 $N$과 $M$이 공백을 사이에 두고 주어진다.

다음 $M$개의 줄에는 도로의 정보가 주어진다. 이 중 $j$ (1ドル ≤ j ≤ M$)번째 줄에는 세 정수 $x_j,ドル $y_j,ドル $t_j$가 공백을 사이에 두고 주어진다.

그다음 줄에는 $N$개의 정수 $c_1 , c_2 , \cdots , c_N$이 공백을 사이에 두고 주어진다.

그다음 줄에는 두 정수 $a,ドル $b$가 공백을 사이에 두고 주어진다.

출력

만약 정올이가 어떻게 이동하더라도 $N$번 건물에 도착할 수 없다면, -1을 출력한다.

그렇지 않다면, 정올이가 $N$번 건물에 도착하기 위해 소요되는 최소 시간을 초 단위로 출력한다. 이 값은 항상 정수임을 증명할 수 있다.

제한

• 주어지는 모든 수는 정수이다
• 3ドル ≤ N ≤ 2,円 000$
• 3ドル ≤ M ≤ 4,円 000$
• 1ドル ≤ j ≤ M$인 각 $j$에 대해 1ドル ≤ x_j , y_j ≤ N,ドル $x_j ≠ y_j,ドル 1ドル ≤ t_j ≤ 100,円 000$
• 1ドル ≤ j < k ≤ M$인 각 $j,ドル $k$에 대해 $(x_j , y_j ) ≠ (x_k , y_k )$. 즉, 두 도로의 시작 건물과 도착 건물이 모두 서로 같은 경우는 없다.
• 2ドル ≤ i ≤ N − 1$인 각 $i$에 대해 $c_i ∈ \{0, 1\}$
• $c_1 = c_N = 0$이다. 즉, 1ドル$번 건물과 $N$번 건물에는 창문이 없다.
• 1ドル ≤ a, b ≤ 10^9$

서브태스크

힌트