#include<bits/stdc++.h>
using namespace std;
#define file(filename) freopen(filename".in","r",stdin),freopen(filename".out","w",stdout)
#define endl "\n"
#define first fi
#define second sc
using ll=long long;using ull=unsigned long long;using ld=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;using vi=vector<int>;using sti=stack<int>;using seti=set<int>;using mii=map<int,int>;using piii=pair<int,pair<int,int> >;using pq=priority_queue<int>;using pqs=priority_queue<int,vector<int>,greater<int> >;
#define mem(a,num) memset(a,num,sizeof(a))
#define sort_(a,n) sort(a+1,a+n+1)
#define sort_cmp(a,n) sort(a+1,a+n+1,cmp)
#define keep(n) fixed<<setprecision(n)
#define LF putchar('\n')
#define SP putchar(' ')
#define debug(x) cout<<#x<<'='<<x<<endl;
#define randint(l,r) rand()%((r)-(l)+1)+(l)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define rush(T) while(T--)
namespace fast_io{
   template <typename T>inline void read(T& x) {x = 0; char ch = getchar();ll f = 1;while (!isdigit(ch)) {if (ch == '-')f *= -1;ch = getchar();} while (isdigit(ch)) {x = x * 10 + ch - 48;ch = getchar();}x *= f;}template <typename T, typename... Args>void read(T& first, Args&... args) {read(first);read(args...);}
   template <typename T>inline void write(T arg) {T x = arg;if (x < 0) {putchar('-');x = -x;}if (x > 9) { write(x / 10);} putchar(x % 10 + '0');}template <typename T, typename... Ts>void write(T arg, Ts... args) {write(arg); if (sizeof...(args) != 0) { putchar(' ');write(args...);}}
   inline __int128 rd(){__int128 sum=0,fl=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()){if(ch=='-')fl=-1;}for(;isdigit(ch);ch=getchar()){sum=sum*10+ch-'0';}return sum*fl;}
   template <typename T>inline void readA(T x[],int len){for(int i=1;i<=len;i++){read(x[i]);}}
   inline void readS(string &s){char ch=getchar();while(ch==' '||ch=='\n') {ch=getchar();}while(ch!=' '&&ch!='\n') {s+=ch,ch=getchar();}}
   inline void readSL(string &s){char ch=getchar();while(ch=='\n') {ch=getchar();}while(ch!='\n') {s+=ch,ch=getchar();}}
   inline void readC(char s[]){int tot=0;char ch=getchar();while(ch==' '||ch=='\n') {ch=getchar();}while(ch!=' '&&ch!='\n') {s[tot++]=ch,ch=getchar();}}
   inline void writeS(string s){int len=s.length();for(int i=0;i<len;i++){putchar(s[i]);}}
   inline void readD(double &x){scanf("%lf",&x);}
   inline void writeD(double x){printf("%lf",x);}
   inline void keepD(double x,int len){printf("%.*lf",len,x);}
   inline void writeC(char s[],int len){for(int i=0;i<len;i++){putchar(s[i]);}}
   template <typename T>inline void readV(vector<T> &v,int n){for(int i=1;i<=n;i++){T x;read(x);v.push_back(x);}}
   template <typename T>inline void writeA(T x[],int len){for(int i=1;i<=len;i++){write(x[i]),SP;}}
   template <typename T>inline void writeV(vector<T> &v,int n){for(int i=1;i<=n;i++){write(v[i]),SP;}}
   inline void readc(char &x){x=getchar();}template <typename T, typename... Args>void readc(T & first, Args &... args) {readc(first);readc(args...);}
   inline void writec(char x){putchar(x);}template <typename T, typename... Ts>void writec(T arg, Ts... args) {writec(arg); if (sizeof...(args) != 0) { putchar(' ');writec(args...);}}
   inline char rdc(){return getchar();}
}using namespace fast_io;
const int N=501,INF=0x3f3f3f3f;
int match[N];//右点匹配了哪个左点 
int va[N],vb[N];//标记是否在交替路中
ll la[N],lb[N];//左顶标，右顶标
ll w[N][N],d[N];//维护更新的delta值
ll n,m,ans;
struct s{
	int l,r;
//	bool operator <(const s &a)const{
//		return this->l<a.l;
//	}
}match2[N];
bool cmp(const s &a,const s &b){return a.l<b.l;}
bool dfs(int x){
	va[x]=1;//x在交替路中
	for(int y=1;y<=n;y++){
		if(!vb[y]){
			if(la[x]+lb[y]-w[x][y]==0){//相等子图 
				vb[y]=1;//y在交替路中
				if(!match[y]||dfs(match[y])){
					match[y]=x;//配对 
					return 1;
				} 
			}
		}else d[y]=min(d[y],la[x]+lb[y]-w[x][y]);//不是相等子图则记录最小的d[y]
	}return 0;
} 
ll KM(){
	//左顶标取i的出边的最大边权
	mem(match,0);
	for(int i=1;i<=n;i++) la[i]=-INF,lb[i]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) la[i]=max(la[i],w[i][j]);
	}for(int i=1;i<=n;i++) lb[i]=0;
	for(int i=1;i<=n;i++){
		while(1){//直到左点i找到匹配 
			fill(va+1,va+n+1,0);
			fill(vb+1,vb+n+1,0);
//			fill(d+1,d+n+1,INF);
			if(dfs(i))break;
			ll delta=INF;
			for(int j=1;j<=n;j++){
				if(!vb[j]) delta=min(delta,d[j]);
			}for(int j=1;j<=n;j++){//修改顶标 
				if(va[j]) la[j]-=delta;
				if(vb[j]) lb[j]+=delta;
			}
		}
	}ll res=0;
	for(int i=1;i<=n;i++) res+=w[match[i]][i];
	return res; 
}//复杂度O(n^4) 


int main() {
    //file("");
    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	read(n);
	rep(i,1,n) rep(j,1,n) w[i][j]=rd();
	ans=KM();
	write(ans),LF;
	rep(i,1,n) match2[i].l=match[i],match2[i].r=i;
	sort_cmp(match2,n);
	rep(i,1,n){
		int t=w[match2[i].l][match2[i].r];
          w[match2[i].l][match2[i].r]=-INF;
          if(KM()<ans)write(match2[i].l,match2[i].r),LF;
          w[match2[i].l][match2[i].r]=t;
	}	
    return 0;
}