#include<bits/stdc++.h>
using namespace std;
int n,m,c[100005],u,v,w;
struct data{int to,w;};
vector<data>h[1000005];
queue<int>Q;
int dis[100005];
bool fa[10005];
int main()
{
	cin>>n>>m;
	memset(dis,63,sizeof dis);
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		h[u].push_back((data){v,w+c[v]});
		h[v].push_back((data){u,w+c[u]});
	}
	Q.push(1);
	dis[1]=0;
	fa[1]=1;
	while(Q.size())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<=h[x].size();i++)
		{
			int to=h[x][i].to,w=h[x][i].w;
			if(dis[to]>dis[x]+w)
			{
				dis[to]=dis[x]+w;
				if(fa[to]==0)
				{
					Q.push(to);
					fa[to]=1;
				}
			}
		}
	}
	cout<<dis[n]-c[n];
	return 0;
}