#include <bits/stdc++.h>
using namespace std;
void printQ(priority_queue <array <int, 4>> q) {
	while (!q.empty()) {
		cout << "  " << q.top()[0] << " " << q.top()[1] << " " << q.top()[2] << " " << q.top()[3] << endl;
		q.pop();
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	const bool debug = false;
	int n, m; cin >> n >> m;
	vector <int> dist(n, -1);
	vector <set <array <int, 2>>> ngb(n+1);
	//vector <bool> visited(n, false);
	//set <array <int, 2>> visited;
	map <array <int, 2>, bool> visited;
	priority_queue <array <int, 4>> q;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		q.push({-x, i, i, 0});
		ngb[i].insert({n, x});
	}
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		ngb[a].insert({b, c});
		ngb[b].insert({a, c});
	}
	if (debug) printQ(q);
	while (!q.empty()) {
		int x = q.top()[1];
		int d = q.top()[0];
		int v = q.top()[2];
		int c = q.top()[3];
		q.pop();
		//if (visited[x]) continue;
		if (visited[{x, v}]) continue;
		if (debug) cout << "at " << x << " with " << d << " ngb[x].size(): " << ngb[x].size() << endl;
		if (x == n) {
			cout << -d << endl;
			return 0;
		}
		//visited[x] = true;
		visited[{x, v}] = true;
		//visited.insert({x, p})
		for (auto edge : ngb[x]) {
			int y = edge[0], w = edge[1];
			if (debug) cout << ' ' << y << ' ' << w;
			if (y != n || c) {
				if (debug) cout << "  -" << endl;
				q.push({d-w, y, v, c+1});
			} else if (debug) cout << endl;
		}
		if (debug) printQ(q);
	}

	return 0;
}