#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;

using LL = long long int;

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

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

int w[N];

pair <LL, int> heap[N];
int s;

void push(pair<LL, int> x){
	heap[s+1] = x;
	int pos = s+1;
	s++;
	while(pos > 1 && heap[pos].first > heap[pos/2].first){
		swap(heap[pos], heap[pos/2]);
		pos /= 2;
	}
}

pair<LL, int> top(){
	return heap[1];
}

bool empty(){
	return s == 0;
}


void pop(){
	swap(heap[1], heap[s]);
	s--;
	int pos = 1;
	while(2*pos <= s){
		if(2*pos+1 <= s){
			if(max(heap[2*pos].first, heap[2*pos+1].first) > heap[pos].first){
				if(heap[2*pos+1].first > heap[2*pos].first){
					swap(heap[2*pos+1], heap[pos]);
					pos = 2*pos+1;		
				}
				else{
					swap(heap[2*pos], heap[pos]);
					pos = 2*pos;
				}
			}
		}
		else{
			if(heap[2*pos].first > heap[pos].first){
				swap(heap[2*pos], heap[pos]);
				pos = 2*pos;
			}
		}
	}
}



void dijkstra(int root, int n){
	for(int i = 0; i < n; i++){
		dist[i] = INF;
	}
	dist[root] = 0;
	push({0, root});
	while(!empty()){
		int v = top().second;
		pop();
		if(!vis[v]){
			vis[v] = true;
			for(auto [u, c]: V[v]){
				if(dist[u] > dist[v]+c){
					dist[u] = dist[v]+c;
					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;
}