program ing;

const dx:array[1..4] of -1..1 =(1,0,-1,0);

dy:array[1..4] of -1..1 =(0,-1,0,1);

type node=record

x,y:integer;

k:longint;

end;

var b:array[1..200000] of node;

a:array[0..310,0..310] of integer;

i,t,x,y,m:integer;

w:boolean;

procedure doit;

var f,t:longint;

i,j,k,x,y,x1,y1:integer;

q:boolean;

begin

f:=0; t:=1;

b[1].x:=0; b[1].y:=0; b[1].k:=0;

repeat

f:=f+1;

for i:=1 to 4 do begin

x:=b[f].x+dx[i];

y:=b[f].y+dy[i];

if (x>=0) and (y>=0) and (y<=301) and (x<=301) and (a[x,y]<>-1) then begin

if (a[x,y]-b[f].k>=3) or (a[x,y]=0) then begin

k:=0; q:=false;

for j:=1 to 4 do begin

x1:=x+dx[j];

y1:=y+dy[j];

if (x1>=0) and (y1>=0) and (x1<=301) and (y1<=301) then

if ((a[x1,y1]=-1) or (a[x1,y1]=0) or

(a[x1,y1]>b[f].k+1)) then k:=k+1;

if (x1=-1) or (y1=-1) or (x1=302) or (y1=302) then k:=k+1;

end;

if k=4 then begin

t:=t+1;

b[t].x:=x; b[t].y:=y; b[t].k:=b[f].k+1;

if a[x,y]=0 then a[x,y]:=-1;

q:=true;

end;

k:=0;

if q and (a[x,y]=-1) then for j:=1 to 4 do begin

x1:=b[t].x+dx[j];

y1:=b[t].y+dy[j];

if (x1>=0) and (y1>=0) and (x1<=301) and (y1<=301) then

if (a[x1,y1]=0) or (a[x1,y1]=-1) then k:=k+1;

if (x1=-1) or (y1=-1) or (x1=302) or (y1=302) then k:=k+1;

end;

if k=4 then begin writeln(b[t].k); w:=false; exit; end;

end;

end;

end;

until f=t;

end;

begin

readln(m);

for i:=1 to m do begin

readln(x,y,t);

a[x,y]:=t;

end;

w:=true;

if (a[0,0]<>1) or (a[0,0]=0) then doit;

if w then writeln(-1);

end.