#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void rd(T &x)
{
	x=0;bool f=0;char c=getchar();
	while(!isdigit(c)) {if(c=='-') f=1;c=getchar();}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;
}
#define int long long
typedef long long ll;
const int N=1005,M=2e6+5,inf=0x7fffffff;
struct node{int x,y,z;}e[M];
int n,m,tot=1,ver[M],nxt[M],edge[M],h[N],flow[M],c[N],d[N],Flow;ll dis[N][2],mxflow;bool vis[N];
inline void add(int x,int y,int z,int c) 
{
	ver[++tot]=y,edge[tot]=z,flow[tot]=c,nxt[tot]=h[x],h[x]=tot;
	ver[++tot]=x,edge[tot]=z,flow[tot]=0,nxt[tot]=h[y],h[y]=tot;
}
void dijkstra(int s,int k)
{
	memset(vis,0,sizeof(vis));
	priority_queue<pair<int,int>>q;
	q.push({0,s});dis[s][k]=0;
	while(q.size())
	{
		int u=q.top().second;q.pop();
		if(vis[u]) continue;vis[u]=1;
		for(int i=h[u];i;i=nxt[i])
		{
			int v=ver[i],w=edge[i];
			if(dis[v][k]>dis[u][k]+w) 
			{
				dis[v][k]=dis[u][k]+w;
				q.push({-dis[v][k],v});
			}
		}
	}
}
int s,t;
bool bfs()
{
	memset(d,0,sizeof(d));
	queue<int>q;
	q.push(s);d[s]=1;
	while(q.size())
	{
		int u=q.front();q.pop();
		for(int i=h[u];i;i=nxt[i])
			if(flow[i] && !d[ver[i]] && dis[u][0]+edge[i]+dis[ver[i]][1]==dis[t][0])
			{
				d[ver[i]]=d[u]+1;
				if(ver[i]==t) return 1;
				q.push(ver[i]);
			}
	}
	return 0;
}
int dinic(int u,int fl)
{
	if(u==t) return fl;
	int rest=fl;
	for(int i=h[u];i && rest;i=nxt[i])
		if(flow[i] && d[ver[i]]==d[u]+1 && dis[u][0]+edge[i]+dis[ver[i]][1]==dis[t][0])
		{
			int k=dinic(ver[i],min(rest,flow[i]));
			if(!k) d[ver[i]]=0;
			flow[i]-=k,flow[i^1]+=k,rest-=k;
		}
	return fl-rest;
}

signed main()
{
	memset(dis,0x3f,sizeof(dis));
	rd(n),rd(m);for(int i=1;i<=m;i++) rd(e[i].x),rd(e[i].y),rd(e[i].z);
	for(int i=1;i<=n;i++) rd(c[i]);s=0,t=n+n+1;c[1]=c[n]=inf;
	for(int i=1;i<=n;i++) add(i,i+n,0,c[i]),add(i+n,i,0,c[i]);
	for(int i=1;i<=m;i++) add(e[i].x+n,e[i].y,e[i].z,inf),add(e[i].y+n,e[i].x,e[i].z,inf);
	add(s,1,0,inf);add(n+n,t,0,inf);add(1+n,s,0,inf);add(t,n,0,inf);
	dijkstra(s,0),dijkstra(t,1);
	while(bfs()) while(Flow=dinic(s,inf)) mxflow+=Flow;
	printf("%lld\n",mxflow);
	return 0;
}

只过了一个点，不知道是不是思路错了，望大佬帮忙差错