#include <bits/stdc++.h>

using namespace std;

int a[][],pos[],ok=,f[];

int o[];

vector<int> h[];

set<int> s[];

set<int>::iterator it;

long long d[][];

void dfs(int u,int fa)

{

    f[u]=fa;

    if(ok==-) return ;

    if(h[u].size()>)

    {

        ok=-;

        return ;

    }

    int k=;

    for(int i=; i<h[u].size(); i++)

    {

        int v=h[u][i];

        if(v==fa) continue;

        k++;

        while(pos[f[u]]==k||k==pos[u]) k++;

        pos[v]=k;

        s[k].insert(v);

        dfs(v,u);

    }

}

int main()

{

    int n,i,j,x,y;

    scanf("%d",&n);

    for(i=; i<=; i++)

        for(j=; j<=n; j++) scanf("%d",&a[i][j]);

    for(i=; i<n; i++)

    {

        scanf("%d%d",&x,&y);

        h[x].push_back(y);

        h[y].push_back(x);

    }

    s[].insert();

    pos[]=;

    dfs(,);

    if(ok==-) return puts("-1"),;

    for(i=; i<=; i++)

        for(it=s[i].begin(); it!=s[i].end(); it++)

        {

            d[i][]+=a[][*it];

            d[i][]+=a[][*it];

            d[i][]+=a[][*it];

        }

    long long mmin;

    mmin=d[][]+d[][]+d[][];

    mmin=min(mmin,d[][]+d[][]+d[][]);

    mmin=min(mmin,d[][]+d[][]+d[][]);

    mmin=min(mmin,d[][]+d[][]+d[][]);

    mmin=min(mmin,d[][]+d[][]+d[][]);

    mmin=min(mmin,d[][]+d[][]+d[][]);

    printf("%lld\n",mmin);

    if(mmin==d[][]+d[][]+d[][]) o[]=,o[]=,o[]=;

    else if(mmin==d[][]+d[][]+d[][]) o[]=,o[]=,o[]=;

    else if(mmin==d[][]+d[][]+d[][]) o[]=,o[]=,o[]=;

    else if(mmin==d[][]+d[][]+d[][]) o[]=,o[]=,o[]=;

    else if(mmin==d[][]+d[][]+d[][]) o[]=,o[]=,o[]=;

    else if(mmin==d[][]+d[][]+d[][]) o[]=,o[]=,o[]=;

    for(i=;i<=n;i++) printf("%d ",o[pos[i]]);

    return ;

}