Cod sursa(job #271048)
const inf=1000000;
const nmax=500;
var f,h:text;
ok:boolean;
g:array[1..2*nmax] of record
x,y,cost:longint;
end;
df,d,p:array[1..nmax]of longint;
s:array[1..nmax]of 0..1;
c,x1,x,y,min,n,i,m,j,k:longint;
i1,t:byte;
begin
assign(f,'distante.in');
reset(f);
assign(h,'distante.out');
rewrite(h);
readln(f,t);
for i1:=1 to t do
begin
readln(f,n,m,x1);
for i:=1 to n do
read(f,df[i]);
for i:=1 to m do
begin
read(f,x,y,c);
g[i].x:=x;
g[i].y:=y;
g[i].cost:=c;
if x=x1 then d[y]:=c;
end;
for i:=1 to n do
if (x1<>i) and (d[i]=0) then d[i]:=inf;
repeat
ok:=true;
for i:=1 to m do
if d[g[i].y]>(d[g[i].x]+g[i].cost) then
begin
d[g[i].y]:=d[g[i].x]+g[i].cost;
ok:=false;
end;
until ok;
for i:=1 to n do
if (d[i]<>df[i]) or ((d[i]=inf) and (df[i]<>0)) then
begin
ok:=false;
break;
end;
if ok then writeln(h,'DA')
else writeln(h,'NU');
end;
close(h);
end.