User's AC Ratio in this contest

0.0% (0/9)

Submission's AC Ratio in this contest

0.0% (0/31)

Description

在經過之前多輪的超時空跳躍下，學員們終於成功在編號 C8763 的時空裡把小嵐堵在資訊大樓裡了，雖然已經知道小嵐躲在哪間教室了，但因為進行了太多次時空跳躍導致現在的時間與空間變得十分不穩定，所以沒有辦法依靠正常的道路爬上資訊大樓去逮住小嵐。

現在總共有 $N$ 間教室編號 $1$ 到 $N$，分別散落在 $L$ 層，位於同一層的教室皆不相通，但每層的任意教室都可以花費長度為 $C$ 的時間通到上一層或下一層的任意教室，除了上下相通外因為時空錯亂的原因還會多出額外的 $M$ 條道路，每條道路都會連接一對 $u, v$ 代表編號為 $u, v$ 之間的教室存在一條道路，且經過該道路需要花費 $w$ 的時間。

已知小嵐在編號為 $N$ 的教室而學員們在編號為 $1$ 的教室，現在你需要找出一條花費時間最短的路徑從學員們的教室通到小嵐的教室，否則小嵐就會帶著大家的期末分數捲分潛逃。

Input Format

第一行有三個整數 $N, M, C$ 分別代表有 $N$ 間教室 $M$ 條道路，以及任意教室通到上一層或下一層任意教室需要花費長度為 $C$ 的時間移動。
第二行有 $N$ 個數字，第 $i$ 個數字代表第 $i$ 間教室所屬的樓層為 $l_i$。
接下來 $M$ 行，每行有 $u, v, w$ 三個數代表 $u, v$ 之間存在一條道路，且經過該道路需要花費 $w$ 的時間

$1\leq N, M\leq 2\times 10^5$
$1\leq C\leq 10^3$
$1\leq L\leq N, 1\leq l_i\leq L$
$1\leq u, v\leq N, 1\leq w\leq 10^4$

Output Format

輸出從第 $1$ 間教室到第 $N$ 間教室的最短路徑需花費的時間長，如果不存在則輸出 $-1$。

Sample Input 1

3 3 3
1 2 3
1 2 1
1 3 4
2 3 1

Sample Output 1

Sample Input 2

4 2 5
1 2 4 4
1 2 1
3 4 5

Sample Output 2

-1

Sample Input 3

4 3 5
1 1 4 4
1 2 3
3 4 2
1 3 1

Sample Output 3

Hints

你已經被期末好運貓貓造訪了，擼擼牠然後對著牠喵一聲你就會期末歐趴

Problem Source

Subtasks

No.	Testdata Range	Score
1	0~26	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	2000	65536	65536	1
1	2000	65536	65536	1
2	2000	65536	65536	1
3	2000	65536	65536	1
4	2000	65536	65536	1
5	2000	65536	65536	1
6	2000	65536	65536	1
7	2000	65536	65536	1
8	2000	65536	65536	1
9	2000	65536	65536	1
10	2000	65536	65536	1
11	2000	65536	65536	1
12	2000	65536	65536	1
13	2000	65536	65536	1
14	2000	65536	65536	1
15	2000	65536	65536	1
16	2000	65536	65536	1
17	2000	65536	65536	1
18	2000	65536	65536	1
19	2000	65536	65536	1
20	2000	65536	65536	1
21	2000	65536	65536	1
22	2000	65536	65536	1
23	2000	65536	65536	1
24	2000	65536	65536	1
25	2000	65536	65536	1
26	2000	65536	65536	1

Submit

Status

Ranklist

136 . 時空旅人小嵐