var n,i,x,y,t,j,q1,q2,q3,t1,x1,y1:longint;
a:array[-1..301,-1..301,1..2] of longint;
b:array[1..10000000,1..2] of longint;
begin
readln(n);
for i:=1 to n do begin
readln(x,y,t);
a[x,y,1]:=1;
a[x,y,2]:=t;
for j:=1 to 4 do begin
a[x+fx[j,1],y+fx[j,2],1]:=1;
a[x+fx[j,1],y+fx[j,2],2]:=t;
end;
end;
q1:=1;
q2:=1;
if a[0,0,1]<>0 then while q1<=q2 do begin
q3:=q2+1;
inc(t1);
for i:=q1 to q2 do begin
for j:=1 to 4 do begin
x1:=b[i,1]+fx[j,1];
y1:=b[i,2]+fx[j,2];
if (x1>=0)and(x1<301)and(y1>=0)and(y1<301)and((a[x1,y1,1]=0)or(a[x1,y1,2]>t1)) then begin
if a[x1,y1,1]=0 then begin
writeln(t1);
halt;
end;
inc(q2);
b[q2,1]:=x1;
b[q2,2]:=y1;
a[x1,y1,1]:=1;
a[x1,y1,2]:=1;
end;
end;
end;
q1:=q3;
end else begin
writeln(0);
halt;
end;
writeln(-1);
end.
var t,n,ans:longint;
begin
readln(n);
ans:=1;
t:=0;
repeat
n:=n-ans;
inc(t);
inc(ans);
if ans>n then ans:=0;
until n=0;
writeln(t);
end.