المسألة

ضلّ الثعبان JOI-kun طريقه ودخل إلى قصر كبير. وقبل أن يكتشفه سكان القصر، يجب عليه الهروب منه.

يوجد في هذا القصر $N$ غرفة مرقمة $1, 2, \dots, N$. كما يوجد $M$ ممراً، ويربط الممر الـ $i$ ($1 \le i \le M$) بين الغرفة $A_i$ والغرفة $B_i$. يستطيع JOI-kun عبور هذه الممرات في كلا الاتجاهين، ويستغرق عبور الممر $i$ مدة $D_i$ دقيقة. ولا توجد أي وسيلة للتنقل بين الغرف سوى عبر الممرات.

تُضبط درجة حرارة كل غرفة في هذا القصر عند مستوى ثابت؛ وهي بالنسبة لـ JOI-kun إما باردة جداً، أو مريحة، أو حارة جداً. ولأن JOI-kun لا يتحمل التغيرات المفاجئة في درجة الحرارة، فلا يمكنه دخول غرفة حارة جداً قبل مرور $X$ دقيقة على الأقل منذ آخر مرة غادر فيها غرفة باردة جداً. وبالمثل، لا يمكنه دخول غرفة باردة جداً قبل مرور $X$ دقيقة على الأقل منذ آخر مرة غادر فيها غرفة حارة جداً.

أثناء التنقل، يجب على JOI-kun مغادرة الغرفة فوراً بمجرد دخوله إليها. كما لا يمكنه العودة من منتصف الممر، ولا استغراق وقت أطول من $D_i$ دقيقة لعبور الممر $i$. ومع ذلك، يُسمح له بدخول غرفة سبق أن زارها مرة أخرى، أو استخدام ممر سبق أن عبره مرة أخرى.

يوجد JOI-kun حالياً في الغرفة $1$. وهذه الغرفة باردة جداً بالنسبة لـ JOI-kun. وبمجرد دخول JOI-kun إلى الغرفة $N$ حيث يقع مخرج القصر، يتمكن من الهروب من القصر.

أوجد أقصر وقت يلزم JOI-kun للهروب من القصر.

الإدخال

يتكون الإدخال من $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-kun يحتاج إلى $X$ دقيقة للتكيف مع تغير درجة الحرارة.

وفي السطر $i$ ($1 \le i \le N$) من الأسطر الـ $N$ التالية، كُتب عدد صحيح $T_i$ ($0 \le T_i \le 2$) يمثل درجة حرارة الغرفة $i$. بالنسبة لـ JOI-kun، تكون الغرفة $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-kun يستطيع الهروب من القصر.

الإخراج

اطبع في سطر $1$ عدداً صحيحاً يمثل أقل عدد من الدقائق اللازمة لهروب JOI-kun من القصر.

أمثلة الإدخال والإخراج

مثال الإدخال 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$).