#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
/* *
 *
 * Too many mind, no mind.
 *
 * */
const int maxn = 1e4 + 10, logn = 32, oo = 1e9;
using pii = pair <int, int>;
int par[maxn], depth[maxn], up[maxn][32]; 
long long weight[maxn], dis[maxn];
vector <pii> graph[maxn]; 
vector <int> tree[maxn];
void dfs(int u, int prev) {
	up[u][0] = prev;
	for (int i = 1; i < logn; i++) {
		up[u][i] = up[up[u][i - 1]][i - 1];
	}
	for (int& v : tree[u]) {
		if (v == prev) continue;
		depth[v] = depth[u] + 1;
		dfs(v, u);
	}
}
int lca(int u, int v) {
	if (depth[v] > depth[u]) swap(u, v);
	for (int i = 0; i < logn; i++) {
		if ((depth[u] - depth[v]) >> i & 1) u = up[u][i];
	}
	if (u == v) return u;
	for (int i = logn - 1; i >= 0; i--) {
		if (up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
	}
	return up[u][0];
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, m; cin >> n >> m;
	int root = n; 
	long long mn = oo;
	for (int i = 0; i < n; i++) {
		cin >> weight[i];
		graph[i].push_back({weight[i], root});
		graph[root].push_back({weight[i], i});
		dis[i] = oo;
		mn = min(mn, weight[i]);
	}
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		graph[u].push_back({w, v});
		graph[v].push_back({w, u});
	}
	priority_queue <pii, vector <pii>, greater <pii>> q;
	q.push({0, root});
	while (!q.empty()) {
		int u = q.top().second;
		long long d = q.top().first;
		q.pop();
		if (dis[u] < d) continue;
		for (auto& e : graph[u]) {
			int v = e.second, w = e.first;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				par[v] = u;
				q.push({dis[v], v});
			}
		}
	}
	for (int i = 0; i < n; i++) {
		tree[i].push_back(par[i]);
		tree[par[i]].push_back(i);
	}
	for (int i = 0; i < maxn; i++) for (int j = 0; j < logn; j++) up[i][j] = root;
	dfs(root, root);
	long long ans = oo;
	for (int i = 0; i < n; i++) {
		if (up[i][0] != root) ans = min(ans, dis[i] + weight[i]);
		for (auto& e : graph[i]) {
			int v = e.second, w = e.first;
			if (v == root) continue;
			int a = lca(i, v);
			if (a == v) continue;
			if (a == i) ans = min(ans, dis[v] + weight[v]);
			else if (a == root) ans = min(ans, dis[i] + w + dis[v]);
			else ans = min(ans, dis[i] + w + weight[v]);
			//cout << i << ' ' << v << ' ' << a << ' ' << ans << endl;
		}
	}
	if (!m) ans = 2 * mn;
	cout << ans << '\n';
	return 0;
}