Description

小祥平時的工作是在樂團裡彈鋼琴,但是彈琴賺的錢不夠多,除了在客服打工還有陪初華散步外,小祥會當 F1 的賽車手,小祥的賽車叫阿倍姆基。

因為小祥樓樓上的鄰居是從昨天開始才看 F1,所以小祥要講解 F1 賽車的規則:有 $N$ 個站點與 $M$ 條雙向賽道,每條雙向賽道連接兩個站點 $u_i,v_i$,並且長度為 $w_i$ 公里。所有站點是連通的,代表任兩個站點可以經過一系列賽道到達。

小祥要從站點 $1$ 開她的賽車阿倍姆基到站點 $N$,她會攜帶 $L$ 罐氮氣,每罐氮氣會有一個係數 $a_i$,代表用了這罐氮氣後賽車 $1$ 公里只要開 $a_i$ 秒。小祥會從第 $1$ 罐氮氣依序往後使用,每次要經過一個賽道時,假設目前用完 $k-1$ 罐氮氣輪到第 $k$ 罐氮氣,小祥可以做以下的動作:丟掉 $p$($0\le p$) 罐氮氣,並使用目前的氮氣 $a_{k+p}$ 開過賽道,一罐氮氣在開完一個賽道後就會消耗完畢,下一次使用時會從 $a_{k+p+1}$ 開始看。如果過程中不在站點 $N$ 且已經用完 $L$ 罐氮氣了,代表阿倍姆基卡在原地,小祥會被罰錢,為了不讓小祥被罰錢,$N-1\le L$,代表小祥在不丟掉氮氣的情況下,可以從站點 $1$ 開到站點 $N$。

小祥的成績計算方式是開過的賽道裡花的時間最久的那個,也就是假設小祥在從站點 $1$ 開到站點 $N$ 的過程中開過了 $S$ 條賽道,編號分別是 $x_1\sim x_S$,使用氮氣的編號分別是 $y_1\sim y_S$,那她的成績會是 $\max\limits_{i=1}^ S(w_{x_i} \cdot a_{y_i})$。
為了贏過東京阿儂大車隊,小祥想要成績越小越好,請你幫幫她算出最小可以是多少!

Input Format

第一行會有兩個整數 $N$, $M$, $L$。
第二行會有 $L$ 個整數 $a_1\sim a_L$。
接下來 $M$ 行,第 $i$ 行會輸入三個正整數 $u_i,v_i,w_i$。

對於所有測試資料:

  • $2 \leq N\leq 10 ^ 5 $
  • $N-1\le M\le 10^ 5$
  • $N-1 \leq L \leq 3\times 10 ^ 5 $
  • $1 \leq a_i \leq 10 ^ 9 $
  • $1 \leq u_i,v_i \leq N$
  • $1\leq w_i\leq 10 ^ 9 $
  • 保證輸入是一張簡單連通圖

Output Format

輸出一個整數代表小祥的成績最小是多少。

Sample Input 1

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

Sample Output 1

5

Sample Input 2

10 9 15
14 45 132 43 12 31 43 12 1 34 12 3 12 8 12
1 2 22
2 3 34
3 4 48763
4 5 241
5 6 234
6 7 45
7 8 43
8 9 123
9 10 134

Sample Output 2

48763

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0, 2~6 $a_i=1$ 7
3 0, 2~11, 47 $a_i\geq a_{i+1}$ 遞減 14
4 1, 12~16, 47 輸入的圖為一條鏈,$M=N-1,u_i=i.v_i=i+1$ 21
5 0~1, 17~21, 47 $N,M,L \leq 3000$ 11
6 0~1, 17~26, 47 $N,M\leq 3000$ 17
7 0~47 無其他限制 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 2 3 5 6 7
1 4000 262144 65536 1 4 5 6 7
2 4000 262144 65536 2 3 7
3 4000 262144 65536 2 3 7
4 4000 262144 65536 2 3 7
5 4000 262144 65536 2 3 7
6 4000 262144 65536 2 3 7
7 4000 262144 65536 3 7
8 4000 262144 65536 3 7
9 4000 262144 65536 3 7
10 4000 262144 65536 3 7
11 4000 262144 65536 3 7
12 4000 262144 65536 4 7
13 4000 262144 65536 4 7
14 4000 262144 65536 4 7
15 4000 262144 65536 4 7
16 4000 262144 65536 4 7
17 4000 262144 65536 5 6 7
18 4000 262144 65536 5 6 7
19 4000 262144 65536 5 6 7
20 4000 262144 65536 5 6 7
21 4000 262144 65536 5 6 7
22 4000 262144 65536 6 7
23 4000 262144 65536 6 7
24 4000 262144 65536 6 7
25 4000 262144 65536 6 7
26 4000 262144 65536 6 7
27 4000 262144 65536 7
28 4000 262144 65536 7
29 4000 262144 65536 7
30 4000 262144 65536 7
31 4000 262144 65536 7
32 4000 262144 65536 7
33 4000 262144 65536 7
34 4000 262144 65536 7
35 4000 262144 65536 7
36 4000 262144 65536 7
37 4000 262144 65536 7
38 4000 262144 65536 7
39 4000 262144 65536 7
40 4000 262144 65536 7
41 4000 262144 65536 7
42 4000 262144 65536 7
43 4000 262144 65536 7
44 4000 262144 65536 7
45 4000 262144 65536 7
46 4000 262144 65536 7
47 4000 262144 65536 3 4 5 6 7