뱀 JOI 군은 큰 저택에 길을 잃었다. 저택 사람에게 들키기 전에 빠져나가야 한다. 저택에는 방이 \(N\)개 있고 \(1, 2, \ldots, N\)번이 붙어 있다. 복도는 \(M\)개 있고, \(i\)번째 복도(\(1 \le i \le M\))는 방 \(A_i\)와 방 \(B_i\)를 잇는다. JOI 군은 이 복도를 어느 쪽으로든 지날 수 있고, 복도 \(i\)를 지나는 데 \(D_i\)분이 걸린다. 방과 방 사이를 복도 말고 다른 방법으로 이동할 수는 없다. 각 방의 온도는 일정하게 맞춰져 있어, JOI 군에게는 너무 춥거나, 쾌적하거나, 너무 덥다. JOI 군은 갑작스러운 온도 변화에 적응하지 못하므로, 마지막으로 너무 추운 방을 나온 뒤 \(X\)분이 지나기 전에 너무 더운 방에 들어갈 수 없다. 마찬가지로, 마지막으로 너무 더운 방을 나온 뒤 \(X\)분이 지나기 전에 너무 추운 방에 들어갈 수도 없다. 이동 중에 방에 들어가면 바로 방을 나가야 한다. 복도 한가운데에서 되돌아가거나, 복도 \(i\)를 \(D_i\)분보다 오래 걸려 지날 수도 없다. 다만 한 번 들른 방에 다시 들어가거나, 한 번 쓴 복도를 다시 쓰는 것은 된다. JOI 군은 지금 방 \(1\)에 있다. 이 방은 JOI 군에게 너무 춥다. 출구가 있는 방 \(N\)에 들어가면 저택을 탈출할 수 있다. JOI 군이 저택을 탈출하는 데 걸리는 가장 짧은 시간을 구하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(M\) \(X\)
\(T_1\)
\(T_2\)
\(\vdots\)
\(T_N\)
\(A_1\) \(B_1\) \(D_1\)
\(\vdots\)
\(A_M\) \(B_M\) \(D_M\)
- 입력은 \(1+N+M\)줄이다.
- 첫째 줄에 정수 \(N\), \(M\), \(X\)가 공백 하나로 구분되어 주어진다. 저택에 방 \(N\)개와 복도 \(M\)개가 있고, JOI 군이 온도 변화에 적응하는 데 \(X\)분이 걸림을 나타낸다.
- 이어지는 \(N\)줄 중 \(i\)번째 줄(\(1 \le i \le N\))에 방 \(i\)의 온도를 나타내는 정수 \(T_i\)가 주어진다. JOI 군에게 방 \(i\)는 \(T_i = 0\)이면 너무 춥고, \(T_i = 1\)이면 쾌적하고, \(T_i = 2\)이면 너무 덥다. \(T_1 = 0\)임이 보장된다.
- 이어지는 \(M\)줄 중 \(j\)번째 줄(\(1 \le j \le M\))에 정수 \(A_j\), \(B_j\), \(D_j\)가 공백 하나로 구분되어 주어진다. 복도 \(j\)가 방 \(A_j\)와 방 \(B_j\)를 잇고, 지나는 데 \(D_j\)분이 걸림을 나타낸다. 같은 방 쌍을 잇는 복도가 여러 개일 수 있다.
- \(2 \le N \le 10000\)
- \(1 \le M \le 20000\)
- \(1 \le X \le 200\)
- \(0 \le T_i \le 2\)
- \(1 \le A_j < B_j \le N\)
- \(1 \le D_j \le 200\)
- JOI 군이 저택을 탈출할 수 있음이 보장된다.
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에, JOI 군이 저택을 탈출하는 데 걸리는 가장 짧은 시간(분)을 출력한다.
방을 \(1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8\) 순으로 이동하는 것이 가장 짧다.
같은 방 쌍을 잇는 복도가 여러 개인 경우가 있다. 예를 들어 방 \(1\)과 방 \(5\)를 잇는 복도가 둘이다.