C 國有n 個大城市和m 條道路，每條道路連接這n 個城市中的某兩個城市。任意兩個城市之間最多只有一條道路直接相連。這m 條道路中有一部分為單向通行的道路，一部分為雙向通行的道路，雙向通行的道路在統(tǒng)計條數(shù)時也計為1 條。

C 國幅員遼闊，各地的資源分布情況各不相同，這就導(dǎo)致了同一種商品在不同城市的價格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。

商人阿龍來到 C 國旅游。當(dāng)他得知同一種商品在不同城市的價格可能會不同這一信息之后，便決定在旅游的同時，利用商品在不同城市中的差價賺回一點旅費。設(shè)C 國n 個城市的標(biāo)號從1~ n，阿龍決定從1 號城市出發(fā)，并最終在n 號城市結(jié)束自己的旅行。在旅游的過程中，任何城市可以重復(fù)經(jīng)過多次，但不要求經(jīng)過所有n 個城市。阿龍通過這樣的貿(mào)易方式賺取旅費：他會選擇一個經(jīng)過的城市買入他最喜歡的商品——水晶球，并在之后經(jīng)過的另一個城市賣出這個水晶球，用賺取的差價當(dāng)做旅費。由于阿龍主要是來C 國旅游，他決定這個貿(mào)易只進(jìn)行最多一次，當(dāng)然，在賺不到差價的情況下他就無需進(jìn)行貿(mào)易。

假設(shè) C 國有5 個大城市，城市的編號和道路連接情況如下圖，單向箭頭表示這條道路為單向通行，雙向箭頭表示這條道路為雙向通行。

假設(shè) 1~n 號城市的水晶球價格分別為4，3，5，6，1。阿龍可以選擇如下一條線路：1->2->3->5，并在2 號城市以3 的價格買入水晶球，在3號城市以5 的價格賣出水晶球，賺取的旅費數(shù)為2。

阿龍也可以選擇如下一條線路 1->4->5->4->5，并在第1 次到達(dá)5 號城市時以1 的價格買入水晶球，在第2 次到達(dá)4 號城市時以6 的價格賣出水晶球，賺取的旅費數(shù)為5。

現(xiàn)在給出 n 個城市的水晶球價格，m 條道路的信息（每條道路所連接的兩個城市的編號以及該條道路的通行情況）。請你告訴阿龍，他最多能賺取多少旅費。

第一行包含 2 個正整數(shù)n 和m，中間用一個空格隔開，分別表示城市的數(shù)目和道路的數(shù)目。

第二行 n 個正整數(shù)，每兩個整數(shù)之間用一個空格隔開，按標(biāo)號順序分別表示這n 個城市的商品價格。

接下來 m 行，每行有3 個正整數(shù)，x，y，z，每兩個整數(shù)之間用一個空格隔開。如果z=1，表示這條道路是城市x 到城市y 之間的單向道路；如果z=2，表示這條道路為城市x 和城市y 之間的雙向道路。

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

5

【數(shù)據(jù)范圍】

輸入數(shù)據(jù)保證 1 號城市可以到達(dá)n 號城市。

對于 10%的數(shù)據(jù)，1≤n≤6。

對于 30%的數(shù)據(jù)，1≤n≤100。

對于 50%的數(shù)據(jù)，不存在一條旅游路線，可以從一個城市出發(fā)，再回到這個城市。

對于 100%的數(shù)據(jù)，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市水晶球價格≤100。