題目描述

身為一條蛇嘅 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 君喺移動途中一入到某間房就必須即刻離開嗰間房。另外，佢唔可以喺走廊中途掉頭，亦都唔可以用多過 $D_i$ 分鐘嘅時間行過走廊 $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$ 分鐘。

喺接住落嚟 $N$ 行入面嘅第 $i$ 行（$1 \le i \le N$），寫有代表房間 $i$ 溫度嘅整數 $T_i$（$0 \le T_i \le 2$）。對 JOI 君嚟講，房間 $i$ 喺 $T_i = 0$ 嗰陣太凍，喺 $T_i = 1$ 嗰陣舒適，喺 $T_i = 2$ 嗰陣太熱。保證 $T_1 = 0$。

喺接住落嚟 $M$ 行入面嘅第 $j$ 行（$1 \le j \le 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$）之間有幾條走廊連接住。