unittest
{
	assert( [ "3", "1 2 300", "3 3 600", "1 4 800" ].solve == "2900\n900\n0\n0" );
	assert( [ "5", "3 5 400", "5 3 700", "5 5 1000", "5 7 700", "7 5 400" ].solve == "13800\n1600\n0\n0\n0\n0" );
	assert( [ "6", "2 5 1000", "5 2 1100", "5 5 1700", "-2 -5 900", "-5 -2 600", "-5 -5 2200" ].solve == "26700\n13900\n3200\n1200\n0\n0\n0" );
	assert( [ "8", "2 2 286017", "3 1 262355", "2 -2 213815", "1 -3 224435", "-2 -2 136860", "-3 -1 239338", "-2 2 217647", "-1 3 141903" ].solve == "2576709\n1569381\n868031\n605676\n366338\n141903\n0\n0\n0" );
}



import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	auto xyps = new long[ 3 ][ n ];
	foreach( ref xyp; xyps )
	{
		input.popFront;
		xyp = input.front.split.to!( long[] );
	}
	
	// 縦の鉄道を引くパターンごとに、各集落が横方向に移動する場合の歩行距離を計算
	auto vss = new long[][]( 1L << n, n );
	{
		auto ds = new long[ n ];
		foreach( ref d, xyp; lockstep( ds, xyps ) )
		{
			d = abs( xyp[ 0 ] ) * xyp[ 2 ];
		}
		foreach( b, ref vs; vss )
		{
			vs = ds.dup;
			foreach( i, xyp_a; xyps )
			{
				if( ( b & ( 1L << i ) ) == 0 ) continue;
				foreach( ref d, xyp_b; lockstep( vs, xyps ) )
				{
					d = min( d, abs( xyp_a[ 0 ] - xyp_b[ 0 ] ) * xyp_b[ 2 ] );
				}
			}
		}
	}
	
	// 横の鉄道を引くパターンごとに、各集落が縦方向に移動する場合の歩行距離を計算
	auto hss = new long[][]( 1L << n, n );
	{
		auto ds = new long[ n ];
		foreach( ref d, xyp; lockstep( ds, xyps ) )
		{
			d = abs( xyp[ 1 ] ) * xyp[ 2 ];
		}
		foreach( b, ref hs; hss )
		{
			hs = ds.dup;
			foreach( i, xyp_a; xyps )
			{
				if( ( b & ( 1L << i ) ) == 0 ) continue;
				foreach( ref d, xyp_b; lockstep( hs, xyps ) )
				{
					d = min( d, abs( xyp_a[ 1 ] - xyp_b[ 1 ] ) * xyp_b[ 2 ] );
				}
			}
		}
	}
	
	// 全住民の歩行距離合計の最小を計算
	auto anss = new long[ n + 1 ];
	anss[] = long.max;
	solve2( anss, vss, hss, 0, 0, 0, 0 );
	return anss.to!( string[] ).join( "\n" );
}

void solve2( ref long[] anss, long[][] vss, long[][] hss, long vb, long hb, long c, long i )
{
	if( i + 1 < anss.length )
	{
		// i番目の集落に縦の鉄道を引くとき
		solve2( anss, vss, hss, vb | ( 1L << i ), hb, c + 1, i + 1 );
		
		// i番目の集落に横の鉄道を引くとき
		solve2( anss, vss, hss, vb, hb | ( 1L << i ), c + 1, i + 1 );
		
		// i番目の集落に鉄道を引かないとき
		solve2( anss, vss, hss, vb, hb, c, i + 1 );
	}
	else
	{
		// c本の鉄道を引いた場合の全住民の歩行距離合計を計算
		auto s = 0L;
		foreach( v, h; lockstep( vss[ vb ], hss[ hb ] ) )
		{
			s += min( v, h );
		}
		anss[ c ] = min( anss[ c ], s );
	}
}
