小祥平時的工作是在樂團裡彈鋼琴，但是彈琴賺的錢不夠多，除了在客服打工還有陪初華散步外，小祥會當 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})$。
為了贏過東京阿儂大車隊，小祥想要成績越小越好，請你幫幫她算出最小可以是多少！
第一行會有兩個整數 $N$, $M$, $L$。
第二行會有 $L$ 個整數 $a_1\sim a_L$。
接下來 $M$ 行，第 $i$ 行會輸入三個正整數 $u_i,v_i,w_i$。
對於所有測試資料：
輸出一個整數代表小祥的成績最小是多少。
| 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 |