(N,),*XYP = $<.map{|ln| ln.split.map(&:to_i) }

X = XYP.product(XYP).map{|(t,_,_),(x,y,p)|
	(x-t).abs*p
}.each_slice(N).to_a
X << X[-1] if 0<N&1
Y = XYP.product(XYP).map{|(_,t,_),(x,y,p)|
	(y-t).abs*p
}.each_slice(N).to_a
Y << Y[-1] if N&1<1
XY = [*X,Y[0],*Y]

St = Struct.new :a,:k
S = [Float::INFINITY]*(N+1)

st0 = St.new(XYP.map{|x,y,p| [x.abs,y.abs].min*p },0)
S[0] = st0.a.sum
v1,v2 = [st0],[st0]
XY.each_slice(2){|x1,x2|
	v1.concat v1.map{|st|
		if st.k<N
			st = St.new(st.a.map.with_index{|a,i| [a,x1[i]].min },st.k+1)
			s = st.a.sum
			S[st.k] = s if s<S[st.k]
		end
		next st
	}
	v2.concat v2.map{|st|
		if st.k<N
			st = St.new(st.a.map.with_index{|a,i| [a,x2[i]].min },st.k+1)
			s = st.a.sum
			S[st.k] = s if s<S[st.k]
		end
		next st
	}
}

p *S
