/*
  Author : EnderDeer
  OnlineJudge : Luogu
*/

#include<bits/stdc++.h>

#define int long long

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
	int to;
	int nxt;
	int w;
}e[800010];

struct nodde{
	int x;
	int y;
	int op;
}pic[1000010];

int cnt,head[800010];
int n,m;
int a[1000010];
int dis[1000010];
bool bk[1000010];

void add(int x,int y,int w){
	cnt ++;
	e[cnt].to = y;
	e[cnt].nxt = head[x];
	e[cnt].w = w;
	head[x] = cnt;
}

void spfa(){
	queue <int> q;
	for(int i = 1;i <= 3 * n;i ++)dis[i] = 2147483647;
	dis[1] = 0;
	bk[1] = true;
	q.push(1);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		bk[x] = false;
		for(int i = head[x];i;i = e[i].nxt){
			if(dis[x] + e[i].w < dis[e[i].to]){
				dis[e[i].to] = dis[x] + e[i].w;
				if(!bk[e[i].w]){
					q.push(e[i].to);
					bk[e[i].to] = true;
				}
			}
		}
	}
}

signed main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i ++)a[i] = read();
	for(int i = 1;i <= m;i ++){
		pic[i].x = read();
		pic[i].y = read();
		pic[i].op = read();
	}
	for(int i = 1;i <= m;i ++){
		if(pic[i].op == 1){
			add(pic[i].x,pic[i].y,0);
			add(pic[i].x + n,pic[i].y + n,0);
			add(pic[i].x + n * 2,pic[i].y + n * 2,0);
			add(pic[i].x,pic[i].y + n,a[pic[i].x]);
			add(pic[i].x + n,pic[i].y + n + n,-a[pic[i].x]);
		}
		else {
			add(pic[i].x,pic[i].y,0);
			add(pic[i].y,pic[i].x,0);
			add(pic[i].x + n,pic[i].y + n,0);
			add(pic[i].y + n,pic[i].x + n,0);
			add(pic[i].x + n * 2,pic[i].y + n * 2,0);
			add(pic[i].y + n * 2,pic[i].x + n * 2,0);
			add(pic[i].x,pic[i].y + n,a[pic[i].x]);
			add(pic[i].y,pic[i].x + n,a[pic[i].x]);
			add(pic[i].x + n,pic[i].y + n + n,-a[pic[i].x]);
			add(pic[i].y + n,pic[i].x + n + n,-a[pic[i].x]);
		}
	}
	spfa();
	cout<<-dis[3 * n];
	return 0;
}