#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int main() {
	const int INF = 1e9;
	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> dian(n);
	vector<vector<tuple<int, int>>> G(n); // [u] -> <v, w>
	for (int i = 0; i < n; ++i)
		scanf("%d", &dian[i]);
		
	for (int i = 0, u, v, w; i < m; ++i) {
		scanf("%d %d %d", &u, &v, &w);
		--u, --v;
		G[u].push_back(make_tuple(v, w + dian[v]));
		G[v].push_back(make_tuple(u, w + dian[u]));
	}
	
	// [L, 点]
	priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>> pq;
	vector<int> dis(n, INF);
	dis[0] = 0;
	pq.push(make_tuple(0, 0));
	while (pq.size()) {
		int d, x;
		tie(d, x) = pq.top();
		pq.pop();
		
		if (d > dis[x]) {
			if (x == n - 1)
				break;
			continue;
		}
		
		for (auto& it : G[x]) {
			int dx = d + get<1>(it);
			if (dx < dis[get<0>(it)]) {
				dis[get<0>(it)] = dx;
				pq.push(make_tuple(dx, get<0>(it)));
			}
		}
	}
	
	printf("%d\n", dis[n - 1] - dian[n - 1]);
	return 0;
}