Problem K: 旅游1

Problem K: 旅游1

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 44  Solved: 13
[Submit] [Status] [Web Board] [Creator:]

Description

L国有n个城市(编号1~n),城市之间通过m条道路连接,有单向路也有双向路,现在奥利奥在L国旅游,机智的奥利奥发现L国的翡翠在每个城市的价格是不同的,也就是说奥利奥可以通过倒卖翡翠赚取旅费。
奥利奥从1号城市出发,在n号城市结束旅行,交易最多进行一次(一次只能倒卖一个翡翠),城市可以重复经过。
现给出m条路,每个城市翡翠的价格,请帮奥利奥算出他能赚到的最多旅费。

Input

第一行包含2个正整数n和m,中间用一个空格隔开,分别表示城市的数目和道路的数目。
第二行n个正整数,每两个正整数之间用一个空格隔开,按标号顺序分别表示这n个城市的商品价格。
接下来m行,每行有3个正整数,x,y,z,每两个整数之间用一个空格隔开。如果z=1,表示这条道路是城市x到城市y之间的单向道路;如果z=2,表示这条道路为城市x和城市y之间的双向道路。
1≤n≤100000,1≤m≤500000,1≤x,y≤n,1≤z≤2,1≤各城市翡翠价格≤100。

Output

一个整数,赚取的最大旅费。

Sample Input Copy

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

Sample Output Copy

5