#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 150005
#define M 300005
int n,m,head[N],tot,dis[N];
bool vis[N];
struct node{
	int to,next,w;
	node (int to=0,int next=0,int w=0)
		:to(to),next(next),w(w){}
}e[M];
ll read(){
	ll w=0,f=1;
	char ch=getchar();
	while (ch>'9'||ch<'0'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w*f;
}
void adde(int u,int v,int w){
	e[++tot]=node(v,head[u],w);
	head[u]=tot;
}
void spfa(){
	for (int i=1;i<=3*n;i++) dis[i]=999999999;
	queue<int> q;
	q.push(1);
	dis[1]=0;
	while (!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for (int i=head[u];i;i=e[i].next){
			int v=e[i].to,w=e[i].w;
			if (dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if (!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			} 
		}
	}
}
int main(){
	freopen("keepsake.in","r",stdin);
	freopen("keepsake.out","w",stdout);
	n=read(),m=read();
	for (int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		adde(u,v,w),adde(u+n,v+n,w),adde(u+n*2,v+n*2,w);
	}
	for (int i=1;i<=n;i++){
		int a=read();
		adde(i,i+n,a),adde(i+n,i+2*n,-a);
	}
	spfa();
	printf("%d\n",dis[n*3]);
	return 0;
}