#include <bits/stdc++.h>
using namespace std;

using LL = long long int;

const int N = 10007;
const LL INF = 100000000000000007;

LL dist[N];
vector <pair<int, int> > V[N];

int w[N];

void dijkstra(int root, int n){
	for(int i = 0; i < n; i++){
		dist[i] = INF;
	}
	dist[root] = 0;
	priority_queue <pair<LL, int> > Q;
	Q.push({0, root});
	while(!Q.empty()){
		int v = Q.top().second;
		LL D = -Q.top().first;
		Q.pop();
		if(D == dist[v]){
			for(auto [u, c]: V[v]){
				if(dist[u] > D+c){
					dist[u] = D+c;
					Q.push({-dist[u], u});
				}
			}
		}
	}
}

int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> w[i];
	}
	for(int i = 0; i < m; i++){
		int a, b, e;
		cin >> a >> b >> e;
		V[a].push_back({b, e});
		V[b].push_back({a, e});
	}
	LL ans = INF;
	
	for(int i = 0; i < n; i++){
		dijkstra(i, n);
		for(int j = 0; j < n; j++){
			if(j == i) continue;
			ans = min(ans, w[i]+dist[j]+w[j]);
		}
	
	}
	cout << ans << '\n';

	return 0;
}