记录编号	71608	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.260 s
提交时间	2013-10-10 16:48:43	内存使用	5.38 MiB

Program sl;
  var
    h,w,q,max,min:array[0..100000]of longint;
    ne,ver:array[0..500000]of longint;
    v:array[0..100000]of boolean;
    tol,n,m,x,y,z,i,head,tail:longint;
  procedure add(x,y:longint);
    begin
      inc(tol);
      ver[tol]:=y;
      ne[tol]:=h[x];
      h[x]:=tol;
    end;
  begin
    assign(input,'trade.in');
    reset(input);
    assign(output,'trade.out');
    rewrite(output);
    read(n,m);
    for i:=1 to n do
      begin
        read(w[i]);
        min[i]:=w[i];
      end;
    for i:=1 to m do
      begin
        readln(x,y,z);
        add(x,y);
        if z=2 then add(y,x);
      end;
    q[1]:=1;
    v[1]:=true;
    head:=0;
    tail:=1;
    fillchar(max,sizeof(max),$ff);
    max[1]:=0;
    while head<>tail do
      begin
        head:=(head+1)mod n;
        x:=q[head];
        v[x]:=false;
        y:=h[x];
        while y<>0 do
          begin
            z:=ver[y];
            if (max[z]<max[x])or(min[z]>min[x]) then
              begin
                if max[z]<max[x] then max[z]:=max[x];
                if min[z]>min[x] then min[z]:=min[x];
                if w[z]-min[z]>max[z] then max[z]:=w[z]-min[z];
                if not v[z] then
                  begin
                    tail:=(tail+1)mod n;
                    q[tail]:=z;
                    v[z]:=true;
                  end;
              end;
            y:=ne[y];
          end;
      end;
    writeln(max[n]);
    close(input);
    close(output);
  end.