0 Judge
Code: 0
一名奸商佔領了阿源所在的城鎮,開始販售過路卷,我們通過每條道路必須要花費一定的過路卷才能通過,這個城鎮的每個點都有販賣過路卷,只是價錢不一樣,阿源今天要從他家到市集賣東西,請你幫助阿源,找出他從他家到市集所需最少的金額。 這個城鎮總共有$n$個點,$m$條道路,阿源他家在點$1$,市集在點$n$,剛開始擁有$0$張過路卷,每條道路會有一個$w$代表通過這條道路所需的過路卷數量,保證圖連通。
輸入的第一行包含一個正整數 $T(T\leq 10)$,代表接下來有 $T$ 個測試資料。 每筆測試資料第一行會有二個正整數 $n(\leq 2000)$ , $m(\leq 2000)$,代表這座城市有$n$個點,有$m$條雙向道路。 接著會有n個數字$cost_1 cost_2 ... cost_n$,$cost_i(\leq 10^9)$從代表在點$i$過路卷的價格。 接下來會有m行,每行有3個數字$u,v,cost(1\leq u,v \leq n,w\leq 10^4)$代表點$u$跟$v$中間有條雙向道路,且經過這條道路所需的過路卷數量為$w$ 保證任兩個點中間不會有超過一條道路。
輸出一個整數代表從阿源家到市集最少需要的金額,。
$n \leq 100$所有$cost_i$都一樣
$n \leq 2000$ 所有$cost_i$都一樣
$n \leq 500$
無其他限制