program P1053;

Const nn = 1000000000;

Type BAIN = Record

s,t,q:Longint;

End;

Var

i,j,k,s,n,m,p1,p2,q,tf:Longint;

d,w:Array[1..1000,1..1000]of Longint;

b:Array[1..100000]of BAIN;

dist,l,v:Array[1..1000]of Longint;

Procedure DFS(x,y:Longint);

Var

i1,j1:Longint;

Begin

IF v[x]=1 then Exit;

IF (d[x,i]