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

using LL = long long int;

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

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

int w[N];
queue <int> Q[MAXN];
int mw;




void dijkstra(int root, int n){
	for(int i = 0; i < n; i++){
		dist[i] = INF;
	}
	dist[root] = 0;
	int lvl = 0;
	Q[0].push(root);
	int s = 1;
	while(s > 0){
		while(Q[lvl].empty()){
			lvl++;
			if(lvl >= mw) lvl -= mw;
		}
		int v = Q[lvl].front();
		LL D = dist[v];
		Q[lvl].pop();
		s--;
		if(!vis[v]){
			vis[v] = true;
			for(auto [u, c]: V[v]){
				if(dist[u] > D+c){
					dist[u] = D+c;
					int x = lvl+c;
					if(x >= mw) x -= mw;
					Q[x].push(u);
					s++;
				}
			}
		}
	}
}

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});
		mw = max(mw, e);
	}
	LL ans = INF;
	mw++;
	
	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;
}