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

St = Struct.new :a,:k
St0 = St.new(XYP.map{|x,y,p| [x.abs,y.abs].min*p },0)

S = [Float::INFINITY]*(N+1)
S[0] = St0.a.sum
v = [St0]
XYP.each{|x0,y0,|
	v.concat v.map{|st|
		st = St.new(XYP.map.with_index{|(x,_,p),i| [st.a[i],(x-x0).abs*p].min },st.k+1)
		s = st.a.sum
		S[st.k] = s if s<S[st.k]
		next st
	},v.map{|st|
		st = St.new(XYP.map.with_index{|(_,y,p),i| [st.a[i],(y-y0).abs*p].min },st.k+1)
		s = st.a.sum
		S[st.k] = s if s<S[st.k]
		next st
	}
}

p *S
p v.size
