unittest
{
//	assert( [ "5", "1 2", "2 3", "3 4", "4 5", "1 2 3 4 5" ].parse.expand.solve == "10\n1 2 3 4 5" );
	assert( [ "5", "1 2", "2 3", "3 4", "4 5", "1 2 3 4 5" ].parse.expand.solve == "10\n5 4 3 2 1" );
//	assert( [ "5", "1 2", "1 3", "1 4", "1 5", "3141 59 26 53 59" ].parse.expand.solve == "197\n59 26 3141 59 53" );
	assert( [ "5", "1 2", "1 3", "1 4", "1 5", "3141 59 26 53 59" ].parse.expand.solve == "197\n3141 59 59 53 26" );
}



import std.algorithm;
import std.container;
import std.conv;
import std.format;
import std.range;
import std.stdio;
import std.typecons;

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

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	auto abs = new long[ 2 ][ n - 1 ];
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
		ab[] -= 1;
	}
	input.popFront;
	auto cs = input.front.split.to!( long[] );
	return tuple( n, abs, cs );
}

auto solve( long n, long[ 2 ][] abs, long[] cs )
{
	cs.sort!( ( x, y ) => y < x );
	
	// bfsで頂点へ整数を大きい順に書き込む
	auto nss = toAdjacencyList!( true )( n, abs );
	auto m = 0L;
	auto ds = new long[ n ];
	ds[] = long.max;
	
	ds[ 0 ] = cs.front;
	cs.popFront;
	
	auto queue = make!DList( 0L );
	while( !queue.empty )
	{
		auto f = queue.front;
		queue.removeFront();
		
		foreach( t; nss[ f ] )
		{
			if( ds[ t ] < long.max ) continue;
			
			m += cs.front;
			ds[ t ] = cs.front;
			cs.popFront;
			queue.insertBack( t );
		}
	}
	
	return format( "%s\n%s", m, ds.to!( string[] ).join( ' ' ) );
}

// 辺配列から隣接リストを作成
auto toAdjacencyList( bool undirected = false )( long n, long[ 2 ][] es )
{
	auto nss = new long[][ n ];
	foreach( e; es )
	{
		nss[ e[ 0 ] ] ~= e[ 1 ];
		static if( undirected ) nss[ e[ 1 ] ] ~= e[ 0 ];
	}
	return nss;
}
