#include<map>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<algorithm>

using namespace std;

int f[100001][51][2],q[1000001],i,j,k,t,w,dis[100001],n,m,a[100001],diss[100001],x,y,z,u,v,ma=0;

bool exiet[100001];

int main()

{

cin>>n>>m;

for(i=1;i<=n;i++)

scanf("%d",&a[i]);

for(i=1;i<=m;i++)

{

scanf("%d%d%d",&x,&y,&z);

if (z==1)

{

f[x][++f[x][0][0]][0]=y;

f[x][f[x][0][0]][1]=a[y];

}

else if (z==2)

{

f[x][++f[x][0][0]][0]=y;

f[x][f[x][0][0]][1]=a[y];

f[y][++f[y][0][0]][0]=x;

f[y][f[y][0][0]][1]=a[x];

}

}//连边

t=0,w=1;

memset(dis,127/3,sizeof(dis));

q[1]=1;

exiet[1]=true;

do

{

k=q[++t];

for(i=1;i<=f[k][0][0];i++)

{

u=f[k][i][0];

v=f[k][i][1];

if (dis[u]>min(v,dis[k]))

{

dis[u]=min(v,dis[k]);

if (!exiet[u])

{

q[++w]=u;

exiet[u]=true;

}

}

}

exiet[k]=false;

}while (t<w);//从点1开始到每个点买入水晶球的最少花费

memset(exiet,false,sizeof(exiet));

exiet[n]=true;

q[1]=n;

t=0,w=1;

do

{

k=q[++t];

for(i=1;i<=f[k][0][0];i++)

{

u=f[k][i][0];

v=f[k][i][1];

if (diss[u]<max(v,diss[k]))

{

diss[u]=max(v,diss[k]);

if (!exiet[u])

{

q[++w]=u;

exiet[u]=true;

}

}

}

exiet[k]=false;

}while (t<w);//从点N开始在每个点售出水晶球的最少花费

for(i=1;i<=n;i++)

if (abs(dis[i]-diss[i])>ma&&dis[i]<700000000&&diss[i]<700000000) ma=abs(dis[i]-diss[i]);

//dis[i]代表的是1到I的途中买入的水晶球最少的花费，diss[i]代表的是从N到I的途中卖出的水晶球的最高价，两个

//相减的绝对值的最大数就是商人赚取的旅费

cout<<ma<<endl;

}

全错解，不知为何。

求高手看看