RT

# include <iostream>
# include <cstdio>
# include <queue>
# include <cstring>
# include <vector>
# define int long long
using namespace std;
const int maxn = 1000 + 5;
const int maxm = 1e6 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f3f;

int n , m;
int S , T;
int x , y , z;
int a[maxn];
typedef struct {
	int x , y , z , next;
} Edge ;
Edge edge[maxm];
int E = 0 , elast[maxn];
int dis[maxn];
bool vis[maxn];
vector<int> g[maxn];
int cnt[maxn];
void add(int x , int y , int z) {
	E ++;
	edge[E].x = x;
	edge[E].y = y;
	edge[E].z = z;
	edge[E].next = elast[x];
	elast[x] = E;
}
struct Node {
	int k;
	int dis;
	Node (int k_ , int dis_) {
		k = k_;
		dis = dis_;
	}
};
bool operator < (Node a , Node b) {
	return a.dis > b.dis;
}
int dfs(int u , int flow) {
	int temp , delta;
	delta = 0;
	if (u == T) return flow;
	for (int i = elast[u] ; i ; i = edge[i].next) {
		int v = edge[i].y;
		if (edge[i].z > 0 && dis[u] == dis[v] + 1) {
			temp = dfs(v , min(flow - delta , edge[i].z));
			edge[i].z -= temp;
			edge[i ^ 1].z += temp;
			delta += temp;
			if (delta == flow || dis[1] >= T) return delta;
		}
	}
	if (dis[1] >= T) return delta;
	cnt[dis[u]] --;
	if (cnt[dis[u]] == 0) dis[1] = T;
	dis[u] ++;
	cnt[dis[u]] ++;
	return delta;
}
int Isap() {
	int Ans = 0;
	while (dis[1] < T) {
		Ans += dfs(1 , inf + 1);
	}
	return Ans;
}
priority_queue<Node> q;
signed main() {
	scanf("%lld%lld" , &n , &m);
	for (int i = 1 ; i <= m ; i ++) {
		scanf("%lld%lld%lld" , &x , &y , &z);
		add(x , y , z);
		add(y , x , z);
	}
	for (int i = 1 ; i <= n ; i ++) {
		scanf("%lld" , &a[i]);
	}
	for (int i = 1 ; i <= n ; i ++) {
		g[i].clear();
	}
	a[1] = inf;
	a[n] = inf;
	S = 1;
	T = n << 1;
	memset(dis , inf , sizeof dis);
	memset(vis , false , sizeof vis);
	q.push(Node(1 , 0));
	dis[1] = 0;
	while (!q.empty()) {
		int x = q.top().k;
		q.pop();
		if (vis[x]) continue;
		vis[x] = true;
		for (int i = elast[x] ; i ; i = edge[i].next) {
			int y = edge[i].y;
			if (dis[y] > dis[x] + edge[i].z) {
				dis[y] = dis[x] + edge[i].z;
				q.push(Node(y , dis[y]));
			}
		}
	}
	for (int i = 1 ; i <= n ; i ++) {
		for (int j = elast[i] ; j ; j = edge[j].next) {
			int y = edge[j].y;
			int x = i;
			if (dis[y] == dis[x] + edge[j].z) {
				g[x].push_back(y);
			}
		}
	}
	memset(elast , 0 , sizeof elast);
	memset(dis , 0 , sizeof dis);
	E = 0;
	for (int i = 1 ; i <= n ; i ++) {
		add((i - 1) << 1 | 1 , i << 1 , a[i]);
		add(i << 1 , (i - 1) << 1 | 1 , 0);
	}
	for (int i = 1 ; i <= n ; i ++) {
		for (int j = 0 ; j < g[i].size() ; j ++) {
			int End = g[i][j];
			add(i << 1 , (End - 1) << 1 | 1 , inf);
			add((End - 1) << 1 | 1 , i << 1 , 0);
		}
	}
	printf("%lld\n" , Isap());
	return 0;
}