#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+;

const ll INF=1e18;

int fir[N],from[N<<],to[N<<],cntt;

inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; }

int n,cst[N][],ans[][],col[N],pcol[N],du[N];

vector <int> V;

int main()

{

    n=read();

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

        for(int j=;j<=n;j++) cst[j][i]=read();

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

    {

        int a=read(),b=read();

        add(a,b); add(b,a);

        du[a]++; du[b]++;

    }

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

        if(du[i]>) { printf("-1\n"); return ; }

    int rt=; for(int i=;i<=n;i++) if(du[i]==) { rt=i; break; }

    int pre=rt,now=to[fir[rt]]; V.push_back(rt);

    while(du[now]>)

        for(int i=fir[now];i;i=from[i])

        {

            int &v=to[i]; if(v==pre) continue;

            V.push_back(now); pre=now; now=v; break;

        }

    V.push_back(now);

    ll ans=INF;

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

        for(int j=;j<;j++) if(i!=j)

        {

            int len=V.size(); ll res=cst[V[]][i]+cst[V[]][j];

            pcol[V[]]=i; pcol[V[]]=j;

            for(int k=;k<len;k++)

            {

                for(int c=;c<;c++)

                    if(c!=pcol[V[k-]]&&c!=pcol[V[k-]]) pcol[V[k]]=c;

                res+=cst[V[k]][pcol[V[k]]];

            }

            if(res<ans)

                for(int k=;k<len;k++) col[V[k]]=pcol[V[k]];

            ans=min(ans,res);

        }

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

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

    puts(""); return ;

}