#include <bits/stdc++.h>

const int N = 1e4 + 7;
using namespace std;

int wei[N];
std::vector<pair<int,int> > g[N];

int cost[N][2];
int source[N][2];

const int INF = 1e9;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	for(int i = 0; i < n; ++i) {
		cin >> wei[i];
		cost[i][0] = INF;
		cost[i][1] = INF;
		
	}
	int res = INF;
	int mini = *min_element(wei, wei + n);
	
	set<tuple<int,int,int> > kolejka;
		

	for(int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		
		res = min(res, wei[a] + wei[b] + c);
		
		g[a].push_back({b, c});
		g[b].push_back({a, c});
		kolejka.insert({wei[a], a, a});
		kolejka.insert({wei[b], b, b});
		cost[b][0] = wei[b];
		source[b][0] = b;
		cost[a][0] = wei[a];
		source[a][0] = a;
	}
	
	while(kolejka.size()) {
		auto best = *kolejka.begin();
		kolejka.erase(kolejka.begin());
		
		int c = get<0>(best);
		int u = get<1>(best);
		int v = get<2>(best);
		
		for(auto ed : g[v]) {
			int t = ed.first;
			int nc = ed.second + c;
			if(nc < cost[t][0] and source[t][0] != u) {
				kolejka.insert({cost[t][1], source[t][1], t});
				cost[t][1] = cost[t][0];
				source[t][1] = source[t][0];
				cost[t][0] = nc;
				source[t][0] = u;
				
				kolejka.insert({nc, u, t});
			}
			else if(nc < cost[t][1] and source[t][1] != u and u != source[t][0]) {
				kolejka.insert({cost[t][1], source[t][1], t});
				cost[t][1] = nc;
				source[t][1] = u;
				kolejka.insert({nc, u, t});
			}
		}
		
	}
	
	for(int i = 0; i < n; ++i) {
			if(cost[i][1] != INF) {
				res = min(res, cost[i][0] + cost[i][1]);
			}
	}
	
	
	cout << res << '\n';
	
	
}