60005 무궁화 꽃이 피었습니다 Platinum V

문제

KOI 마을은 N개의 건물과 M개의 도로로 구성되어 있다. 건물 1번과 N번에는 창문이 없고, 다른 건물들은 창문이 있거나 없을 수 있다.

정올이는 건물 1번에서 시작하여 N번 건물에 도착해야 하며, 한국이의 시야를 피해야 한다. 한국이는 다음 패턴으로 시선을 반복한다:

• a초 동안 눈을 감음
• b초 동안 눈을 뜸
• 이를 반복

한국이가 눈을 뜨고 있는 동안 정올이가 도로 위 또는 창문이 있는 건물 내부에 있으면, 즉시 발각되어 게임이 종료된다.

입력

첫째 줄에 N, M이 주어진다.

다음 M개의 줄에 도로 정보 (시작건물, 도착건물, 소요시간)가 주어진다.

다음 줄에 각 건물의 창문 유무 c_1, c_2, …, c_N이 주어진다.

마지막 줄에 a, b가 주어진다.

출력

정올이가 N번 건물에 도착 불가능하면 -1, 가능하면 최소 소요 시간을 출력한다.

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 0 0 0
3 8

14

4 4
1 2 3
1 3 4
2 4 3
3 4 1
0 1 1 0
3 8

-1