#include<bits/stdc++.h>
#define re register
using namespace std;
const int maxn=500+10,maxm=25600*2+10,inf=1e18;
int n,m,s,t,cnt=1,ans;
int head[maxn],dis[maxn],h[maxn];
bitset<maxn> vis;
bitset<maxm> check;
bool in[maxn][maxn];
queue<int> q1;
struct node{
	int u,to,nxt,c,w;
	bool op;
}e[maxm<<1],e1[maxm<<1];
struct node1{
	int dis,id;
	bool operator<(const node1 &a)const{
		return a.dis<dis;
	}
};
struct node2{
	int v,e;
}p[maxn];
inline void add(int u,int v,int c,int w){
	++cnt;
	e[cnt].u=u;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].c=c;
	e[cnt].w=w;
	head[u]=cnt;
}
inline void spfa(){
	queue<int> q;
	for(re int i=1;i<=n*2+2;++i) h[i]=inf;
	vis.reset();
	h[s]=0,vis[s]=1;	
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(re int i=head[u];i;i=e[i].nxt){
			if(e[i].op) continue;
			int v=e[i].to;
			if(e[i].c&&h[v]>h[u]+e[i].w){
				h[v]=h[u]+e[i].w;
				if(!vis[v]) vis[v]=1,q.push(v);
			}
		}
	}
}
inline bool dj(){
	priority_queue<node1> q;
	for(re int i=1;i<=n*2+2;++i) dis[i]=inf;
	vis.reset();
	q.push(node1{0,s});
	dis[s]=0;
	while(!q.empty()){
		int u=q.top().id;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(re int i=head[u];i;i=e[i].nxt){
			if(e[i].op) continue;
			int v=e[i].to,w=e[i].w+h[u]-h[v];
			if(e[i].c&&dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				p[v].v=u;
				p[v].e=i;
				if(!vis[v]) q.push(node1{dis[v],v});
			}
		}
	}
	return dis[t]!=inf;
}
inline void add_edge(int u,int v,int c,int w){
	add(u,v,c,w);
	add(v,u,0,-w);
}
inline int mfmc(){
	int mnc=0;
	spfa();
	while(dj()){
		int mnf=inf;
		for(re int i=1;i<=n*2+2;++i) h[i]+=dis[i];
		for(re int i=t;i!=s;i=p[i].v) mnf=min(mnf,e[p[i].e].c);
		for(re int i=t;i!=s;i=p[i].v){
			e[p[i].e].c-=mnf;
			e[p[i].e^1].c+=mnf;
			q1.push(p[i].e);
		}
		mnc+=mnf*h[t];
	}
	return -mnc;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	s=n*2+1,t=n*2+2;
	for(re int i=1;i<=n;++i){
		for(re int j=1,x;j<=n;++j){
			cin>>x;
			add_edge(i,j+n,1,-x);
		}
	}
	for(re int i=1;i<=n;++i) add_edge(s,i,1,0),add_edge(i+n,t,1,0);
	memcpy(e1,e,sizeof e);
	ans=mfmc();
	cout<<ans<<'\n';
	for(re int i=2;i<=cnt;i+=2) if(!e[i].c) check[i]=1;
	for(re int i=2;i<=cnt;i+=2){
		if(check[i]){
			while(!q1.empty()) e[q1.front()].c=e1[q1.front()].c,e[q1.front()^1].c=e1[q1.front()^1].c,q1.pop();
			e[i].op=e[i^1].op=1;
			if(mfmc()<ans) in[e[i].u][e[i].to]=1;
			e[i].op=e[i^1].op=0;
		}
	}
	for(re int i=1;i<=n;++i){
		for(re int j=1;j<=n;++j){
			if(in[i][j+n]) cout<<i<<" "<<j<<'\n';
		}
	}
	return 0;
}