A 國(guó)有 N 個(gè)城市，編號(hào)為 1 . . . N。小明是編號(hào)為 1 的城市中一家公司的員工，今天突然接到了上級(jí)通知需要去編號(hào)為 N 的城市出差。

由于疫情原因，很多直達(dá)的交通方式暫時(shí)關(guān)閉，小明無法乘坐飛機(jī)直接從城市 1 到達(dá)城市 N，需要通過其他城市進(jìn)行陸路交通中轉(zhuǎn)。小明通過交通信息網(wǎng)，查詢到了 M 條城市之間仍然還開通的路線信息以及每一條路線需要花費(fèi)的時(shí)間。

同樣由于疫情原因，小明到達(dá)一個(gè)城市后需要隔離觀察一段時(shí)間才能離開該城市前往其他城市。通過網(wǎng)絡(luò)，小明也查詢到了各個(gè)城市的隔離信息。（由于小明之前在城市 1，因此可以直接離開城市 1，不需要隔離）

由于上級(jí)要求，小明希望能夠盡快趕到城市 N，因此他求助于你，希望你能幫他規(guī)劃一條路線，能夠在最短時(shí)間內(nèi)到達(dá)城市 N。 

第 1 行：兩個(gè)正整數(shù) N, M, N 表示 A 國(guó)的城市數(shù)量，M 表示未關(guān)閉的路線數(shù)量

第 2 行：N 個(gè)正整數(shù)，第 i 個(gè)整數(shù) C_i 表示到達(dá)編號(hào)為 i 的城市后需要隔離的時(shí)間

第 3 . . . M + 2 行：每行 3 個(gè)正整數(shù)，u, v, c，表示有一條城市 u 到城市 v 的雙向路線仍然開通著，通過該路線的時(shí)間為 c

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

13

路線 1：1 -> 2 -> 4，時(shí)間為 4+7(隔離)+3=14

路線 2：1 -> 3 -> 4，時(shí)間為 5+3(隔離)+5=13

對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 1000 , 1 ≤ M ≤ 10000, 1 ≤ C_i ≤ 200, 1 ≤ u, v ≤ N, 1 ≤ c ≤ 1000