#include<bits/stdc++.h>
#define AC return 0;
#define int long long 
#define pii pair<int,int>
#define all(tar) tar.begian(),tar.end()
const int N=1e6+5;
const int inf=1e16; 
using namespace std;
int n,m,t,cnt,s;
pair<int,int>p[N];
int a[N],b[N],c[N],use[3*N],dis[N],pre[N],vis[N],us[N];
struct node{
   int v,w;
   bool operator < (const node &u)const{
      return w>u.w;
   }
};
struct edge{
   int v,w,id;
};
vector<edge>e[N];
void dij(){
   priority_queue<node>q;
   q.push({s,0});
   for(int i=1;i<=(n+1)*n/2;i++) dis[i]=inf,vis[i]=0;dis[s]=0;
   while(q.size()){
      node u=q.top();q.pop();
      if(vis[u.v]) continue;
      vis[u.v]=1;
      int id=u.v,w=u.w;
      for(auto [v,val,bs]:e[id]){
         if(dis[v]>w+val){  
            dis[v]=w+val;
            pre[v]=id;us[v]=bs;
            if(!vis[v]) q.push({v,dis[v]});
         }
      }
   }
}
vector<pair<int,int>>res;
void dfs(int u){
   for(auto [to,w,id]:e[u]){
      if(use[id]) continue;
      use[id]=1;
      dfs(to);
      res.push_back(p[to]);
   }
}
bool cmp(edge x,edge y){
   return p[x.id]>p[y.id];
}
void solve(){
   cin>>n;cnt=0;res.clear();
   for(int i=1;i<=n*n;i++) e[i].clear(),pre[i]=us[i]=0;
   int ans=0;
   for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
         p[(i-1)*n+j]={i,j};
      }
   }
   for(int i=1;i<n;i++){
      for(int j=1;j<=i;j++){
         int w;cin>>w;ans+=w;  
         e[(i-1)*n+j].push_back({i*n+j,w,++cnt});
         e[i*n+j].push_back({(i-1)*n+j,w,cnt});
         //cout<<(i-1)*n+j<<" "<<i*n+j<<endl;
      }
   }
   for(int i=1;i<n;i++){
      for(int j=1;j<=i;j++){
         int w;cin>>w;ans+=w;
         e[(i-1)*n+j].push_back({i*n+j+1,w,++cnt});
         e[i*n+j+1].push_back({(i-1)*n+j,w,cnt});
         //cout<<(i-1)*n+j<<" "<<i*n+j+1<<endl;
      }
   }
   for(int i=2;i<=n;i++){
      for(int j=1;j<i;j++){
         int w;cin>>w;ans+=w;
         e[(i-1)*n+j].push_back({(i-1)*n+j+1,w,++cnt});
         e[(i-1)*n+j+1].push_back({(i-1)*n+j,w,cnt});
         //cout<<(i-1)*n+j<<" "<<(i-1)*n+j+1<<endl;
      }
   }
   for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
         sort(e[(i-1)*n+j].begin(),e[(i-1)*n+j].end(),cmp);
      }
   }
   for(int i=1;i<=cnt;i++) use[i]=0;
   s=1;t=n*n;n*=n;
   dij();
   cout<<ans-dis[t]<<'\n';
   int tmp=t;
   while(tmp!=s){
      //cout<<tmp<<" "<<us[tmp]<<'\n';
      use[us[tmp]]=1;
      tmp=pre[tmp];
   }
   
   dfs(s);res.push_back(p[s]);
   reverse(res.begin(),res.end());
   cout<<res.size()<<'\n';
   for(auto [x,y]:res){
      cout<<x<<" "<<y<<" ";
   }
   cout<<'\n';
}
/*
3
2
3
2
4
2
1
1
1
3
100
100 100
1
100 1
100
100 100
*/
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   int T;
   cin>>T;
   while(T--){
      solve();
   }
   AC
}