这其实不是最短路，是bfs，考虑每个节点x，正图上bfs跑出1-x能经过的最小点权，反图上bfs跑出x-n能经过的最大点权。作差即为答案。

//计算1-x买入的最小价值，x-n卖出的最大价值，作差。 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int head1[100010],head2[100010],dis1[100010],dis2[100010],vis[100010],w[100010];
int ans,idx1,idx2,n,m;
struct node{
    int nxt,to;
}edge1[1000010],edge2[1000010];
void add1(int u,int v)
{
    edge1[++idx1].nxt=head1[u];
    edge1[idx1].to=v;
    head1[u]=idx1;
}
void add2(int u,int v)
{
    edge2[++idx2].nxt=head2[u];
    edge2[idx2].to=v;
    head2[u]=idx2;
}
void bfs1(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis1,0x3f3f3f3f,sizeof(dis1));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head1[x];i;i=edge1[i].nxt)
        {
            int y=edge1[i].to;
            if(min(dis1[x],w[y])<dis1[y])
            {
                dis1[y]=min(dis1[x],w[y]);
                if(!vis[y])
                {
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
}
void bfs2(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis2,-0x3f3f3f3f,sizeof(dis2));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head2[x];i;i=edge2[i].nxt)
        {
            int y=edge2[i].to;
            if(max(dis2[x],w[y])>dis2[y])
            {
                dis2[y]=max(dis2[x],w[y]);
                if(!vis[y])
                {
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);//点权bfs 
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,op;
        scanf("%d%d%d",&u,&v,&op);
        if(op==1)
        {
            add1(u,v);
            add2(v,u);
        }
        else
        {
            add1(u,v);
            add1(v,u);
            add2(u,v);
            add2(v,u);
        }
    }
    bfs1(1);
    bfs2(n);
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dis2[i]-dis1[i]);
    }
    printf("%d",ans);
    return 0;
}