Условие задачи

Змей 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$) соединяют сразу несколько коридоров.