#include<bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define memo(a,v) memset(a,v,sizeof(a))
#define CLR(a) memo(a,0)
#define SET(a) memo(a,-1)
#define pb push_back
#define all(a) a.begin(),a.end()
#define eps (1e-9)
#define inf (1<<29)
#define i64 long long
#define u64 unsigned i64
#define AIN(a,b,c) assert(a<=b && b<=c)
#define MAX 205
typedef pair<int,int> pii;
#define INF (1<<29)
#define pot(i,j) (dist[i] - pi[i] + pi[j])
 
pii parent[MAX];
int pi[MAX];
int cap[MAX][MAX][2],cost[MAX][MAX][2],dist[MAX],N, flow[MAX][MAX][2];
vector<int> gr[MAX];
bool visited[MAX];
bool bf(int s,int t){
    for(int i = 0;i<N;i++){
        dist[i] = inf;
        parent[i].first = -1;
    }
    dist[s] = 0;
    parent[s].first = -2;
    for(int k = 0;k<N-1;k++){
        for(int u = 0;u<N;u++){
            for(int i = 0;i<gr[u].size();i++){
                int v = gr[u][i];
                for(int j = 0;j<2;j++)
                    if(cap[u][v][j] && dist[v]>pot(u,v) + cost[u][v][j]){
                        dist[v] = pot(u,v) + cost[u][v][j];
                        parent[v] = pii(u,j);
                    }
            }
        }
    }
    for(int u = 0;u<N;u++){
            for(int i = 0;i<gr[u].size();i++){
                int v = gr[u][i];
                for(int j = 0;j<2;j++)
                    if(cap[u][v][j] && dist[v]>pot(u,v) + cost[u][v][j]){
                        return false;
                    }
            }
        }
    for(int i = 0;i<N;i++){
        if(dist[i] == inf) continue;
        pi[i] -= dist[i];
    }
    return parent[t].first>=0;
}
bool dijkstra(int s,int t){
    for(int i = 0;i<N;i++){
        dist[i] = inf;
        parent[i].first = -1;
        visited[i] = 0;
    }
    dist[s] = 0;
    parent[s].first = -2;
    while(1){
        int u = -1,mn = inf;
        for(int i = 0;i<N;i++){
            if(!visited[i] && dist[i]<mn){
                mn = dist[i];
                u = i;
            }
        }
        if(u == -1) break;
        visited[u] = 1;
        for(int i = 0;i<gr[u].size();i++){
            int v = gr[u][i];
            if(visited[v]) continue;
            for(int j = 0;j<2;j++)
                if(cap[u][v][j] && dist[v]>pot(u,v) + cost[u][v][j]){
                    dist[v] = pot(u,v) + cost[u][v][j];
                    parent[v] = pii(u,j);
                }
        }
    }
    for(int i = 0;i<N;i++){
        if(dist[i] == inf) continue;
        pi[i] -= dist[i];
    }
    return parent[t].first>=0;
}
bool bfs(int s,int t){
    queue<int> q;
    for(int i = 0;i<N;i++)
        dist[i] = inf,parent[i].first = -1;
    dist[s] = 0;
    parent[s].first = -2;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = 0;i<gr[u].size();i++){
            int v = gr[u][i];
            for(int j = 0;j<2;j++)
                if(cap[u][v][j] && pi[v] - pi[u] + cost[u][v][j] == 0 && dist[v] == inf){
                    parent[v] = pii(u,j);
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
        }
    }
    return parent[t].first>=0;
}
int mcmf(int s,int t){
    int u,v, ret = 0;
    if(!bf(s,t)) return 0;
    while(bfs(s,t)){
        for(int i = 0;i<N;i++){
            for(int j = 0;j<2;j++)
                if(cap[i][t][j]>0 && pi[t] - pi[i] + cost[i][t][j] == 0){
                    int fl = cap[i][t][j];
                    for(v = i,u = parent[v].first;v!=s;v = u, u = parent[v].first){
                        int k = parent[v].second;
                        fl = min(fl,cap[u][v][k]);
 
                    }
                    for(v = i,u = parent[v].first;v!=s;v = u, u = parent[v].first){
                        int k = parent[v].second;
                        cap[u][v][k] -= fl;
                        cap[v][u][1-k] += fl;
                    }
                    cap[i][t][j]-=fl;
                    cap[t][i][1-j] += fl;
                    ret+=fl;
                }
        }
        dijkstra(s,t);
    }
    return ret;
}
inline void addEdge(int u,int v,int cp,int ct){
    gr[u].pb(v);
    cap[u][v][0] = cp;
    cost[u][v][0] = ct;
 
    cap[v][u][1] = 0;
    cost[v][u][1] = -ct;
}
int main(){
 //   freopen("input.in","r",stdin);
  //  freopen("output.ans","w",stdout);
    double cl = clock();
    int t, cs = 1, n,m,source,sink,U,L,nr[MAX],nc[MAX],i,j,a[MAX][MAX], row[MAX],col[MAX], x, y, S[MAX][MAX], T[MAX][MAX];
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        AIN(1,n,100);
        AIN(1,m,n*n);
       // AIN(-1000,L,U);
       // AIN(L,U,1000);
        source = n+n;
        sink = source + 1;
        N = sink + 1;
        for(i = 0;i<n;i++)
            for(j = 0;j<n;j++)
                a[i][j] = inf;
        for(i = 0;i<N;i++){
            nc[i] = 0;
            nr[i] = 0;
            pi[i] = 0;
            gr[i].clear();
            for(j = 0;j<N;j++){
                cost[i][j][0] = cost[i][j][1] = inf;
                cap[i][j][0] = cap[i][j][1] = 0;
               // flow[i][j] = 0;
            }
        }
        int sum = 0;
        for(i = 0;i<m;i++){
            scanf("%d %d",&x,&y);
            AIN(1,x,n);
            AIN(1,y,n);
            x--,y--;
            scanf("%d %d %d",&a[x][y],&S[x][y],&T[x][y]);
            AIN(-1000,S[x][y],T[x][y]);
            AIN(S[x][y],T[x][y],1000);
            AIN(-600,a[x][y],600);
            addEdge(x,y+n,inf,T[x][y] - a[x][y]);
            addEdge(y+n,x,inf,a[x][y] - S[x][y]);
            nr[x]++;
            nc[y]++;
        }
       /* for(i = 0;i<n;i++){
            nr = 0;
            row[i] = 0;
            for(j = 0;j<m;j++){
                scanf("%s",tmp);
                a[i][j] = inf;
                if(tmp[0]=='X') continue;
                a[i][j] = atoi(tmp);
                AIN(-500,a[i][j],500);
                nr ++;
                nc[j]++;
                addEdge(i,j+n,inf,U - a[i][j]);
                addEdge(j+n,i,inf,a[i][j] - L);
            }
            addEdge(source,i,nr,0);
            sum+=nr;
        }*/
        for(i = 0;i<n;i++){
            col[i] = 0;
            row[i] = 0;
            addEdge(source,i,nr[i],0);
            addEdge(i+n,sink,nc[i],0);
        }
        if(mcmf(source,sink) != m){
    //        fprintf(stderr,"Case %d: Impossible\n",cs);
            printf("Unlike\n");
            continue;
        }
     /*   for(i = 0;i<n;i++){
            printf(" %d",pi[i]);
        }
        printf("\n");
        for(j = 0;j<m;j++){
            printf(" %d",pi[j+n]);
        }
        printf("\n");*/
 
        for(i = 0;i<n;i++){
            if(pi[i]<0){
                for(j = 0;j<n;j++)
                    col[j]-= pi[i];
                for(j = 0;j<n;j++)
                    if(i != j)
                        row[j] -= pi[i];
            }
            else row[i]+=pi[i];
        }
        for(i = 0;i<n;i++){
            if(pi[i+n]<0){
                for(j = 0;j<n;j++)
                    row[j]-= pi[i+n];
                for(j = 0;j<n;j++)
                    if(i != j)
                        col[j] -= pi[i+n];
            }
            else col[i]+=pi[i+n];
        }
        sum = 0;
        for(i = 0;i<n;i++){
            for(j = 0;j<n;j++){
                if(a[i][j] == inf){
               //     printf(" #");
                    continue;
                }
                AIN(S[i][j],a[i][j]+row[i] - col[j],T[i][j]);
               // printf(" %d",a[i][j]+row[i] - col[j]);
               sum+=a[i][j]+row[i] - col[j];
            }
           // printf("\n");
        }
      //  fprintf(stderr,"Case %d: %d\n",cs,sum);
        printf("%d\n",sum);
        for(i = 0;i<n;i++){
            if(i)
                printf(" ");
            printf("%d",row[i]);
        }
        printf("\n");
        for(j = 0;j<n;j++){
            if(j)
                printf(" ");
            printf("%d",col[j]);
        }
        printf("\n");
    }
    cl = clock() - cl;
    fprintf(stderr,"%lf\n",cl/CLOCKS_PER_SEC);
    return 0;
}