C++ :

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

const int N=100010;
int n,m,w[N];

queue<int>q;
vector<int>G[N],g[N];
typedef vector<int>::iterator IT;

void init() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for(int i=1;i<=m;i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		g[y].push_back(x);
		if(z==2) {
			G[y].push_back(x);
			g[x].push_back(y);
		}
	}
}

int dp[N];
bool inq[N];

void spfa() {
	memset(dp,0x7f,sizeof(dp));
	q.push(1); inq[1]=true;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		inq[u]=false;
		dp[u]=min(dp[u],w[u]);
		for(IT it=G[u].begin();it!=G[u].end();it++) {
			int v=*it;
			if(dp[v]>dp[u]) {
				dp[v]=dp[u];
				if(inq[v])continue;
				q.push(v); inq[v]=true;
			}
		}
	}
}

bool cover[N];

int work() {
	int ans=0;
	for(int i=1;i<=n;i++)if(cover[i])ans=max(ans,w[i]-dp[i]);
	return ans;
}

void bfs() {
	cover[n]=true;
	q.push(n);
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(IT it=g[u].begin();it!=g[u].end();it++) {
			int v=*it;
			if(!cover[v]) {
				cover[v]=true;
				q.push(v);
			}
		}
	}
}

int main() {
	init();
	spfa();
	bfs();
	printf("%d\n",work());
	return 0;
}

Pascal :

program Project1;
type
  rec = record
    y, n: longint;
  end;
var
  tot, n, m: longint;
  data, link, max, min: array[0..100010] of longint;
  q: array[0..500000] of longint;
  e: array[0..500010] of rec;
procedure make(x, y: longint);
begin
  inc(tot);
  e[tot].y := y;
  e[tot].n := link[x];
  link[x] := tot;
end;
procedure init;
var
  i, x, y, z: longint;
begin
  read(n,m);
  for i := 1 to n do
    begin
      read(data[i]);
      max[i] := -1;
      min[i] := 30000;
    end;
  for i := 1 to m do
    begin
      read(x,y,z);
      make(x,y);
     if z = 2 then make(y,x);
    end;
end;


function gmax(x, y: longint):longint;
begin
  if x > y then exit(x) else exit(y);
end;


function gmin(x, y: longint):longint;
begin
  if x < y then exit(x) else exit(y);
end;


procedure spfa;
var
  t, h, ne: longint;
begin
  t := 1;
  h := 1;
  q[1] := 1;
  max[1] := 0;
  min[1] := data[1];

  while h <= t do
    begin
      ne := link[q[h]];
      while ne <> 0 do
        begin
          if (gmin(min[q[h]],data[e[ne].y]) < min[e[ne].y]) or (gmax(max[q[h]],data[e[ne].y]-min[q[h]]) > max[e[ne].y]) then
            begin
              min[e[ne].y] := gmin(gmin(min[q[h]],data[e[ne].y]),min[e[ne].y]);
              max[e[ne].y] := gmax(gmax(max[q[h]],data[e[ne].y]-min[q[h]]),max[e[ne].y]);
              //if b[e[ne].y] then
                begin
                  inc(t);
                  q[t] := e[ne].y;
                end;
            end;
          ne := e[ne].n;
        end;
      inc(h);
    end;
end;


begin
  init;
  spfa;
  writeln(max[n]);
end.