dijkstra:

#include<bits/stdc++.h>
typedef long long ll;
const int INF=2e8;
const ll LLINF=LLONG_MAX;
const int N=300007;
const int M=2100007;
using namespace std;
void swap(int &a,int &b);
inline int read();
inline int write(int);
int n,m,s,x,y,z;
int head[N],ver[M],ed[M],ne[M],dis[N],tot,price[N];
typedef pair<int,int> PII;
bool vis[N];
void add(int x,int y,int z)
{
    tot++;
    ver[tot]=y;
    ed[tot]=z;
    ne[tot]=head[x];
    head[x]=tot;
}
void dijkstra(int s)
{
    priority_queue<PII,vector<PII>,greater<PII> > q;
    q.push({0,s});
    dis[s]=0;
    while(!q.empty())
    {
        //int x=q.top().first;
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i!=-1;i=ne[i])
        {
            int y=ver[i];
            int z=ed[i];
            if(dis[y]>dis[u]+z)
            {
                dis[y]=dis[u]+z;
                q.push({dis[y],y});
            }
        }
    }
}
int main(int argc,char **argv)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(head,-1,sizeof(head));
    //fill(dis,dis+N,-1000);
    memset(dis,0x3f,sizeof(dis)); 
    n=read();
    m=read();
    //k=read();
    //s=1;
    //t=n;
    for(int i=1;i<=n;i++)
    price[i]=read();
    //for(int i=1;i<=n;i++)
    //write(price[i]);
    for(int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        z=read();
        add(x,    y,    0);
        add(x+n,  y+n,  0);
        add(x+n+n,y+n+n,0);
        if(z==2)
        {
			add(y,    x,    0);
			add(y+n,  x+n,  0);
        	add(y+n+n,x+n+n,0);
		}
    }
    
    dijkstra(1);
	write(-dis[3*n]);
    return 0;
}
inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline int write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return x;
}
void swap(int &a,int &b)
{
    a = a^b;
    b = a^b;
    a = a^b;
}

SPFA:

#include<bits/stdc++.h>
typedef long long ll;
const int INF=2e8;
const ll LLINF=LLONG_MAX;
const int N=300007;
const int M=2100007;
using namespace std;
void swap(int &a,int &b);
inline int read();
inline int write(int);
int n,m,s,x,y,z;
queue<int> q;
int head[N],ver[M],ed[M],ne[M],dis[N],tot,price[N];
typedef pair<int,int> PII;
bool vis[N];
void add(int x,int y,int z)
{
    tot++;
    ver[tot]=y;
    ed[tot]=z;
    ne[tot]=head[x];
    head[x]=tot;
}
void SPFA(int s)
{
    memset(vis,0,sizeof(vis));
    fill(dis,dis+N-1,2147483647);
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=ne[i])
        {
            int v=ver[i];
            int w=ed[i];
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(vis[v]==0)
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main(int argc,char **argv)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(head,-1,sizeof(head));
    //fill(dis,dis+N,-1000);
    memset(dis,0x3f,sizeof(dis)); 
    n=read();
    m=read();
    //k=read();
    //s=1;
    //t=n;
    for(int i=1;i<=n;i++)
    price[i]=read();
    //for(int i=1;i<=n;i++)
    //write(price[i]);
    for(int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        z=read();
        add(x,    y,    0);
        add(x+n,  y+n,  0);
        add(x+n+n,y+n+n,0);
        if(z==2)
        {
			add(y,    x,    0);
			add(y+n,  x+n,  0);
        	add(y+n+n,x+n+n,0);
		}
    }
    for(int i=1;i<=n;i++)
    add(i,i+n,price[i]);
    for(int i=1;i<=n;i++)
    add(i+n,i+n+n,-price[i]);
    SPFA(1);
	write(-dis[3*n]);
    return 0;
}
inline int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline int write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return x;
}
void swap(int &a,int &b)
{
    a = a^b;
    b = a^b;
    a = a^b;
}

求助！！！！！！！