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

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vvi = vector<vi>;

#define f(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define pb emplace_back
#define PB push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define dump(x) cout << #x << "=" << x << endl;

const ll INF = 100000000000;

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m ;
	cin >> n>> m;
	vector<vector<pll>> G(n+1, vector<pll>());
	f(i,0,n)
	{
		int x;
		cin >> x;
		G[n].pb(i,x);
	}
	f(i,0,m)
	{
		int a,b,c;
		cin >> a >> b >> c;
		G[a].pb(b,c);
		G[b].pb(a,c);
	}

	sort(all(G[n]), [](pll &p1, pll &p2){return p1.second < p2.second;});
	vll dist(n+1, INF);
	ll out  = INF;
	ll store;
	f(i,0,m)
	{
		if(G[n][i].second >= out)
			break;
		store = G[n][i].second;
		//dump(store);
		G[n][i].second = INF;
		dist.assign(n ,INF);
		dist[n] = 0 ;
		set<pll> pq;
		f(u,0,n+1)
			pq.emplace(dist[u], u);
		while(!pq.empty())
		{
			auto [d,u] = *pq.begin();
			pq.erase(pq.begin());
			for(auto [v,w] : G[u])
			{
				if(dist[u] + w >= dist[v]) continue;
				pq.erase(pq.find({dist[v], v}));
				dist[v] = dist[u] + w;
				pq.emplace(dist[v], v);
			}
		}
		out = min(out, dist[G[n][i].first]+ store);
		//dump(dist[G[n][i].first]);
		//dump(store);
		G[n][i].second = store;

	}
	cout << out ;


	return 0;
}