1 #include <bits/stdc++.h>
2 using namespace std;
3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
4 #define _rep(i,a,b) for(int i = (a);i > b;i --)
5 #define INF 0x3f3f3f3f
6 #define pb push_back
7 #define maxn 5053900
8 typedef long long ll;
9
10 inline ll read()
11 {
12 ll ans = 0;
13 char ch = getchar(), last = ' ';
14 while(!isdigit(ch)) last = ch, ch = getchar();
15 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
16 if(last == '-') ans = -ans;
17 return ans;
18 }
19 inline void write(ll x)
20 {
21 if(x < 0) x = -x, putchar('-');
22 if(x >= 10) write(x / 10);
23 putchar(x % 10 + '0');
24 }
25 int tot,ver[maxn],Next[maxn],head[maxn],val[maxn];
26 void add(int x,int y,int t)
27 {
28 ver[++tot] = y,Next[tot] = head[x],head[x] = tot,val[tot] = t;
29 }
30 int n,m;
31 int v[maxn];
32 typedef pair<int,int> P;
33 int d[maxn];
34 void shortest_path(int s)
35 {
36 priority_queue<P> que;
37 memset(d,-0x3f,sizeof(d));
38 d[s] = 0;
39 que.push(P {0,s});
40
41 while(!que.empty())
42 {
43 P p = que.top();
44 que.pop();
45 int v = p.second;
46 if(d[v] > p.first) continue;
47 for(int i = head[v]; i; i = Next[i])
48 {
49 int y = ver[i];
50 int w = val[i];
51 if(d[y] < d[v] + w)
52 {
53 d[y] = d[v] + w;
54 que.push(P {d[y],y});
55 }
56 }
57 }
58 }
59 int main()
60 {
61 n = read();
62 m = read();
63 _for(i,1,n+1)
64 v[i] = read();
65 _for(i,1,m+1)
66 {
67 int a = read();
68 int b = read();
69 int c = read();
70 if(c==1)
71 {
72 add(a,b,0);
73 add(n+a,n+b,0);
74 add(2*n+a,2*n+b,0);
75 }
76 else
77 {
78 add(a,b,0);
79 add(b,a,0);
80 add(n+a,n+b,0);
81 add(n+b,n+a,0);
82 add(2*n+b,2*n+a,0);
83 add(2*n+a,2*n+b,0);
84 }
85 }
86 _for(i,1,n+1)
87 {
88 add(i,i+n,-v[i]);
89 add(i+n,i+n*2,v[i]);
90 }
91 shortest_path(1);
92 printf("%d\n",max(0,d[3*n]));
93 return 0;
94 }
