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

#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define FORD(i, a, b) for (int i=(a); i>(b); i--)
#define ALL(w) w.begin(), w.end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define ithBit(m, i) ((m) >> (i) & 1)

const int maxN = 1 << 18;
const long long INF = 1'000'000'000'000'000;

vector <pair <int, int> > G[maxN];
int T[maxN];
int n;
long long res = INF, dist[maxN];
priority_queue <pair <long long, int> > H;

void conn(int a, int b, int c)
{
	G[a].pb({b, c});
	G[b].pb({a, c});
}

void Dijkstra(int b)
{
	FOR(v, 0, n)
		if (ithBit(v, b))
			conn(n, v, T[v]);
			
	fill(dist, dist+n, INF);
	H.push({0, n});
	while (!H.empty())
	{
		auto [d, v] = H.top();
		H.pop();
		if (-d != dist[v])
			continue;
		for (auto [u, e] : G[v])
		{
			if (dist[u] > -d + e)
			{
				dist[u] = -d + e;
				H.push({-dist[u], u});
			}
		}
	}
	
	FOR(v, 0, n)
	{	
		if (ithBit(v, b))
			G[v].pop_back();
		else
			res = min(res, dist[v] + T[v]);
	}
	G[n].resize(0);
}

int main()
{
	int m;
	scanf ("%d%d", &n, &m);
	
	FOR(i, 0, n)
		scanf ("%d", T+i);
	
	while (m--)
	{
		int a, b, c;
		scanf ("%d%d%d", &a, &b, &c);
		conn(a, b, c);
	}
	
	FOR(b, 0, 16)
		Dijkstra(b);
		
	printf("%lld\n", res);
	return 0;
}