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

int n, m, head[50000 + 5], next[100000 + 6], pos = 1, price[50000 + 5], d[50000 + 5], fa[5000 + 5];
int maxn[100000 + 5], minn[100000 + 5];

struct edge{
	int from, to, dist;
}edges[100000 + 5];

struct node{
	int r, d;
	bool operator < (node rhs) const {
		return d > rhs.d;
	}
};

inline void add_edge(int u, int v, int w) {
	edge &e = edges[pos];
	e.from = u; e.to = v; e.dist = w;
	next[pos] = head[u]; head[u] = pos++; 
}

void dijkstra() {
	priority_queue<node> Q;
	Q.push((node){1, 0});
	while(!Q.empty()) {
		int x = Q.top().r; Q.pop();
		for(int i = head[x]; i; i = next[i]) {
			edge &e = edges[i];
			if(d[e.to] > d[x] + e.dist) {
				d[e.to] = d[x] + e.dist;
				fa[e.to] = x;
				Q.push((node){e.to, d[e.to]});
			}
		}
	}
}

int main() {
	freopen("keepsake.in", "r", stdin);
	freopen("keepsake.out", "w", stdout);
	memset(d, 0x7f, sizeof(d));
	d[1] = 0;
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		add_edge(u, v, w);
	}
	for(int i = 1; i <= n; i++) scanf("%d", &price[i]);
	dijkstra();
	vector<int> path;
	int pthis = n;
	while(pthis) {
		path.push_back(pthis);
		pthis = fa[pthis];
	}
	for(int i = 0; i < path.size(); i++) maxn[i + 1] = max(maxn[i], path[i]);
	minn[(int)path.size()] = path.back();
	for(int i = path.size() - 2; i >= 0; i--) minn[i + 1] = min(minn[i + 2], path[i]);
	int ans = -0x7fffffff;
	for(int i = 1; i < n; i++) ans = max(ans, maxn[i] - minn[i + 1]);
	printf("%d", d[n] - ans);
	return 0;
}