#include<iostream>
#include<cstring>
#include<queue>
#include<tuple>
using namespace std;

const int maxn = 1e5 + 5;
const int maxm = 5e5 + 5;
int n, m, cnt, price[maxn], head[maxn], edge[maxm], nex[maxm];
int dist[maxn][3];
void add(int a,int b) {
	edge[++cnt] = b;
	nex[cnt] = head[a];
	head[a] = cnt;
}

void dijkstra() {
	memset(dist, -0x3f, sizeof(dist));
	bool isv[maxn][3];
	memset(isv, 0, sizeof isv);
	dist[1][0] = 0;
	priority_queue<tuple<int, int, int>> q;
	q.push({ 0,0,1 });
	while (q.size()) {
		tuple<int, int, int> temp = q.top();
		q.pop();
		int n0 = get<2>(temp);
		int k0 = get<0>(temp);
		k0 = -k0;
		if (isv[n0][k0])continue;
		isv[n0][k0] = 1;
		for (int i = head[n0]; i; i = nex[i]) {
			int n1 = edge[i];	
			if (dist[n0][k0] > dist[n1][k0]) {
				dist[n1][k0] = dist[n0][k0];
				q.push({ -k0,dist[n1][k0],n1});
			}
		}
		int w1 = price[n0];
		if (k0<2 && dist[n0][k0] + w1 * (k0 == 1 ? 1 : -1) > dist[n0][k0 + 1]) {
			dist[n0][k0 + 1] = dist[n0][k0] + w1 * (k0 == 1 ? 1 : -1);
			q.push({ -(k0 + 1),dist[n0][k0 + 1],n0 });
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> price[i];
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b);
		if (c == 2) {
			add(b, a);
		}
	}
	dijkstra();
	//for (int i = 0; i <= 2; i++) {
	//	for (int j = 1; j <= n; j++) cout << dist[j][i] << " ";
	//	cout << endl;
	//}
	cout << max(dist[n][2],0);
	return 0;
}