Умова задачі

Змій JOI-кун випадково заповз у великий маєток. Поки мешканці маєтку його не помітили, він мусить вибратися звідти.

У цьому маєтку є $N$ кімнат, пронумерованих $1, 2, \dots, N$. Також є $M$ коридорів, і $i$-й коридор ($1 \le i \le M$) з'єднує кімнату $A_i$ та кімнату $B_i$. JOI-кун може рухатися цими коридорами в обох напрямках, і проходження коридором $i$ займає $D_i$ хвилин. Переміщуватися між кімнатами інакше ніж коридорами неможливо.

Температура в кожній кімнаті маєтку підтримується сталою і для JOI-куна є або занадто холодною, або комфортною, або занадто спекотною. Оскільки JOI-кун не переносить різких перепадів температури, він не може зайти в занадто спекотну кімнату раніше ніж за $X$ хвилин після того, як востаннє залишив занадто холодну кімнату. Аналогічно, він не може зайти в занадто холодну кімнату раніше ніж за $X$ хвилин після того, як востаннє залишив занадто спекотну кімнату.

Під час руху, щойно JOI-кун заходить у кімнату, він повинен негайно з неї вийти. Крім того, він не може розвернутися посеред коридору або витрачати на проходження коридору $i$ більше ніж $D_i$ хвилин. Проте дозволяється повторно заходити у вже відвідані кімнати та повторно користуватися вже пройденими коридорами.

Зараз JOI-кун перебуває в кімнаті $1$. Ця кімната для JOI-куна занадто холодна. Щойно JOI-кун потрапить у кімнату $N$, де розташований вихід із маєтку, він зможе втекти.

Знайдіть найкоротший час, потрібний JOI-куну, щоб вибратися з маєтку.

Вхідні дані

Вхідні дані складаються з $1 + N + M$ рядків.

У рядку $1$ через пробіл записано $3$ цілі числа $N, M, X$ ($2 \le N \le 10000$, $1 \le M \le 20000$, $1 \le X \le 200$). Це означає, що в маєтку є $N$ кімнат і $M$ коридорів, а на адаптацію до зміни температури JOI-куну потрібно $X$ хвилин.

В $i$-му рядку ($1 \le i \le N$) із наступних $N$ рядків записано ціле число $T_i$ ($0 \le T_i \le 2$), що позначає температуру кімнати $i$. Для JOI-куна в кімнаті $i$ занадто холодно при $T_i = 0$, комфортно при $T_i = 1$ і занадто спекотно при $T_i = 2$. Гарантується, що $T_1 = 0$.

У $j$-му рядку ($1 \le j \le M$) із наступних $M$ рядків через пробіл записано $3$ цілі числа $A_j, B_j, D_j$ ($1 \le A_j < B_j \le N$, $1 \le D_j \le 200$). Це означає, що коридор $j$ з'єднує кімнату $A_j$ та кімнату $B_j$, і його проходження займає $D_j$ хвилин. Зауважте, що ту саму пару кімнат можуть з'єднувати кілька коридорів.

У заданих вхідних даних гарантується, що JOI-кун може вибратися з маєтку.

Вихідні дані

Виведіть в $1$ рядку ціле число — мінімальну кількість хвилин, необхідну JOI-куну для втечі з маєтку.

Приклади вводу та виводу

Приклад вводу 1

8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2

Приклад виводу 1

9

Приклад вводу 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

Приклад виводу 2

6

У прикладі вводу 1 найшвидше рухатися кімнатами в порядку $1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 5 \to 8$.

У прикладі вводу 2 деякі пари кімнат (наприклад, кімнату $1$ і кімнату $5$) з'єднують одразу кілька коридорів.