program dijkstra;

var a:array[1..1000,0..1000,0..1] of longint;

visit:array[1..1000,1..1000] of boolean;

map:array[1..1000] of longint;

i,j,x,y,n,eye,o:integer;

z,max,t,u:longint;

procedure out(x:integer);

var j,i,p:integer;

min:longint;

begin

min:=10000000;

if x=max then halt else

for j:=1 to a[x,0,0] do

begin

if not visit[eye,a[x,j,0]] then

begin

if eye=x then map[a[x,j,0]]:=a[x,j,1]+t

else

begin

inc(a[eye,0,0]);

a[eye,a[eye,0,0],0]:=a[x,j,0];

a[eye,a[eye,0,0],1]:=a[x,j,1]+t;

if a[eye,a[eye,0,0],1]a[eye,0,0] then else o:=a[eye,0,0]

end

end;

{ru zhan}

end;

end;

for i:=1 to o do

if a[eye,i,0]=0 then else

if (map[a[eye,i,0]]0)and(map[a[eye,i,0]]max then max:=x;

if y>max then max:=y;

inc(a[x,0,0]);

a[x,a[x,0,0],0]:=y;

a[x,a[x,0,0],1]:=z;

end;

{readin}

o:=a[1,0,0];

for i:=1 to 1 do

begin

eye:=i;

out(i);

end;

{done}

close(input);

close(output);

end.