Scanf.scanf "%d" (fun n ->
    let nei = Array.make n [] in
    for i = 1 to n - 1 do
        Scanf.scanf " %d %d" (fun a b ->
            let a = a - 1 in
            let b = b - 1 in
            nei.(a) <- b :: nei.(a);
            nei.(b) <- a :: nei.(b)
        )
    done;
    let c = Array.init n (fun _ -> Scanf.scanf " %d" (fun c -> c)) in
    Array.sort compare c;
    let m = Array.fold_left (+) 0 c - c.(n - 1) in
    Printf.printf "%d\n" m;

    let rec loop i mx mxv =
        if i = n then mxv else
            let l = List.length nei.(i) in
            if l > mx then loop (i + 1) l i else
                loop (i + 1) mx mxv
    in
    let mxv = loop 0 0 0 in

    let v = Array.make n 0 in
    let rec fill cur k =
        List.fold_left (fun k next ->
            if v.(next) = 0 then (v.(next) <- c.(k); fill next (k - 1)) else k) k nei.(cur)
    in
    v.(mxv) <- c.(n - 1);
    fill mxv (n - 2);
    Array.iter (Printf.printf "%d ") v;
    print_newline ()
)