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

using ll = long long;
using vi = vector<int>;
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;

#define int long long
	#define ppi pair<int, pii>

class node
{
	public:
		int dis = -1;
		int typos = -1;
		vi nbs;
		vi ws;
};


signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);


	int n,m ; cin >> n >> m;
	vi dis(n);
	f(i,0,n) cin >> dis[i];
	vector<node> nodes(n);
	f(i,0,m)
	{
		int x, y, z;
		cin >> x >> y >> z;
		nodes[x].nbs.pb(y);
		nodes[y].nbs.pb(x);
		nodes[x].ws.pb(z);
		nodes[y].ws.pb(z);
	}

	int best = -1;

	priority_queue<ppi> q;
	f(i,0,n)
	{
		q.push(ppi(-dis[i], pii(i,i)));
	}
	while(!q.empty())
	{
		ppi top = q.top();
		int dist = -top.first;
		int index = top.second.first;
		int typo = top.second.second;
		q.pop();
		if  (nodes[index].dis == -1)
		{
			nodes[index].dis = dist;
			nodes[index].typos = typo;
			f(i,0,sz(nodes[index].nbs))
			{
				q.push(ppi(-(dist + nodes[index].ws[i]), pii(nodes[index].nbs[i], typo)));
			}
		}
		else if (nodes[index].typos!=typo)
		{
			int total = nodes[index].dis + dist;
			if (best == -1 || total < best)
				best = total;
		}
	}

	cout << best << "\n";


	return 0;
}