#include <iostream>
#include <vector>
#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[3*N];
int s;

static 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;
	}
}

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

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


static void pop(){
	heap[1] = heap[s];
	heap[s] = {0, 0};
	s--;
	int pos = 1;
	while(pos <= s){
		int ls = 2*pos;
		int rs = ls+1;
		int son = (heap[ls].first < heap[rs].first ? rs : ls);
		if(heap[son].first <= heap[pos].first){
			break;
		}
		swap(heap[son], heap[pos]);
		pos = son;
	}
}



static 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});
				}
			}
		}
	
	
	}
}

static inline void read(int * n){
	char c = getchar();
	while(c > '9' || c < '0'){
		c = getchar();
	}
	*n = 0;
	do{
		(*n) *= 10;
		(*n) += c-'0';
		c = getchar();
	}while(c <= '9' && c >= '0');
}


int main(){
	int n, m;
	read(&n);
	read(&m);
	for(int i = 1; i <= n; i++){
		read(&w[i]);
		//V[0].push_back({i, w[i]});
		//V[i].push_back({0, w[i]});
	}
	for(int i = 0; i < m; i++){
		int a, b, e;
		read(&a);
		read(&b);
		read(&e);
		a++;
		b++;
		V[a].push_back({b, e});
		V[b].push_back({a, e});
	}
	LL ans = INF;
	for(int i = 1; i <= n; i++){
		dijkstra(i, n);
		for(int j = i+1; j <= n; j++){
			ans = min(ans, w[i]+dist[j]+w[j]);
		}
	}
	
	
	
	
	
	cout << ans << '\n';
	

	return 0;
}