ll d[800][800],x[800],y[800],t[800];
ll@n;
rep(i,n){
	ll@xi,@yi,@ti;
	x[i]=xi;
	y[i]=yi;
	t[i]=ti;
	ll xyi=xi*xi+yi*yi;
	rep(j,i){
		ll xj=x[j];
		ll yj=y[j];
		ll tj=t[j];
		d[i][j]=d[j][i]=
			ti==tj ?
			(xj-xi)*(xj-xi)+(yj-yi)*(yj-yi) :
			({ ll xyj=xj*xj+yj*yj; xyi+xyj-Isqrt(4*xyi*xyj); });
	}
}
DijkstraHeap<ll>h;
h.malloc(n,1);
h.change(0,0);
for(ll i;i=h.pop(),i!=n-1;){
	rep(j,n){
		h.change(j,max(h.val[i],d[i][j]));
	}
}
wt(h.val[n-1]);