בעיה

הנחש 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 נכנס לחדר עליו לצאת ממנו מיד. בנוסף, הוא אינו יכול להסתובב אחורה באמצע מסדרון, ואינו יכול לעבור במסדרון $i$ במשך זמן ארוך מ-$D_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$).