阳历不过求调

#include<bits/stdc++.h>
using namespace std;
#define t(floor,x) floor*n+x
const int N=1e5+10;
int n,m,x,y,z,ans;
int a[N],dp[N*3];
//dp[i]=j 表示走到 i 的最长路径为 j
bool vis[N*3];
struct Edge{
	int ed,money;
};
vector<Edge> g[N*3];
inline int read()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
void add(int x,int y)
{
	for(int i=1;i<=3;i++)
	{
		g[t(i,x)].push_back({t(i,y),0});
	}
}
void bfs()
{
	for(int i=1;i<=n*3;i++)
	{
		dp[i]=INT_MIN;
	}
	queue<int> q;
	q.push(1);
	dp[1]=0;
	vis[1]=true;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=0;i<g[u].size();i++)
		{
			Edge k=g[u][i];
			if(dp[k.ed]<dp[u]+k.money) 
			{
                dp[k.ed]=dp[k.money]+k.money;
                if(!vis[k.ed])
				{ 
					q.push(k.ed); 
					vis[k.ed]=true; 
				}
            } 
		}
	}
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		g[t(1,i)].push_back({t(2,i),-a[i]});
		g[t(2,i)].push_back({t(3,i),a[i]});
	}
	for(int i=1;i<=m;i++)
	{
		x=read();
		y=read();
		z=read();
		add(x,y);
		if(z==2) add(y,x);
	}
	bfs();
	cout<<dp[t(3,n)];
	return 0;
}