#define INF 0x3f3f3f3f

#include <queue>
#include <cstdio>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

using namespace std;

inline int read(){
	int t = 0;
	register char c = getchar();
	while (c < 48 || c > 57) c = getchar();
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
	return t;
}

inline int max(int a,int b) {return a > b ? a : b;}

struct edge{
	int u,v,w,next;
}e[1000001];

queue <int> q;

int n,m,x,y,z,etot,price[100001],head[300001],dis[300001];
bool vis[300001];

void addedge(int u,int v,int w){
	e[++etot].u = u,e[etot].v = v,e[etot].w = w,e[etot].next = head[u],head[u] = etot;
}

int main(){
	freopen("keepsake.in","r",stdin);
	freopen("keepsake.out","w",stdout);
	memset(dis,63,sizeof(dis));
	n = read(),m = read();
	for (int i = 1;i <= m;i++){
		x = read(),y = read(),z = read();
		addedge(x,y,z),addedge(x + n,y + n,z),addedge(x + (n << 1),y + (n << 1),z);
	}
	for (int i = 1;i <= n;i++) price[i] = read(),addedge(i,i + n,price[i]),addedge(i + n,i + (n << 1),-price[i]);
	q.push(1),vis[1] = 1,dis[1] = 0;
	while (!q.empty()){
		int now = q.front();
		q.pop(),vis[now] = 0;
		for (int i = head[now];i;i = e[i].next){
			if (dis[e[i].v] > dis[now] + e[i].w){
				dis[e[i].v] = dis[now] + e[i].w;
				if (!vis[e[i].v]) q.push(e[i].v),vis[e[i].v] = 1;
			}
		}
	}
	printf("%d",dis[n * 3]);
	return 0;
}