#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
struct Edge
{
	long long v, w;
};
struct Node
{
	long long dis, u;
    bool operator > (const Node &o) const
    {
    	return dis > o.dis;
    }
};
int n, m;
bool vis[N];
long long dis[N];
vector<Edge> e[N];
int p[N], a[N], b[N], c[N];
void dij(int s)
{
	memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    priority_queue<Node, vector<Node>, greater<Node> > q;
    dis[s] = 0;
    q.push({0, s});
    while(q.size())
    {
    	int u = q.top().u; q.pop();
        if(vis[u])continue;
        vis[u] = true;
        for(auto ed : e[u])
        {
        	int v = ed.v, w = ed.w;
            if(dis[v] > dis[u] + w)
            {
            	dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
int main()
{
	cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
    	cin >> p[i];
        e[n + 1].push_back({i, p[i]});
    }
	for(int i = 1; i <= m; i++)
	{
    	cin >> a[i] >> b[i] >> c[i];
        e[a[i]].push_back({b[i], c[i]});
	}
    dij(n + 1);
    cout << dis[n];
}