import java.io.*;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Vector;

public class bugs {

	static class Matrix{
		int matrix[][];
		int size;

		int xy[], yx[];
		boolean vx[], vy[];
		int mr[], mc[];
		int answer;

		Matrix(){
			size=0;
		}

		private int min(int a, int b){
			if (a<b)
				return a;
			else
				return b;
		}
		private int max(int a, int b){
			if (a>b)
				return a;
			else
				return b;
		}

		public void loadGraph()throws IOException{
			BufferedReader in;
			StringTokenizer st;
			in=new BufferedReader(new FileReader("assignment.in"));
			String temp=in.readLine();
			st=new StringTokenizer(temp);
			size=Integer.parseInt(st.nextToken());
			matrix=new int[size][size];
			for (int i=0; i<size; i++){
				temp=in.readLine();
				st=new StringTokenizer(temp);
				for (int j=0; j<size; j++){
					matrix[i][j]=Integer.parseInt(st.nextToken());
				}
			}
			in.close();
		}

		boolean findOus(int i){
			if (vx[i])
				return false;
			vx[i]=true;
			for (int j=0; j<size; j++)
				if (matrix[i][j]-mr[i]-mc[j]==0)
					vy[j]=true;
			for (int j=0; j<size; j++)
				if ((matrix[i][j]-mr[i]-mc[j]==0) && yx[j]==-1) {
					xy[i]=j;
					yx[j]=i;
					return true;
				}
			for (int j=0; j<size; j++)
				if ((matrix[i][j]-mr[i]-mc[j]==0) && findOus(yx[j])) {
					xy[i] = j;
					yx[j] = i;
					return true;
				}
			return false;
		}

		void kuhn(){
			xy=new int[size];
			yx=new int[size];
			vx=new boolean[size];
			vy=new boolean[size];
			mr=new int[size];
			mc=new int[size];
			for (int i=0; i<size; i++){
				mc[i]=Integer.MAX_VALUE;
				mr[i]=Integer.MAX_VALUE;
				xy[i]=-1;
				yx[i]=-1;
				vx[i]=false;
				vy[i]=false;
			}
			for (int i=0; i<size; ++i)
				for (int j=0; j<size; ++j)
					mr[i]=min(mr[i],matrix[i][j]);
			for (int j=0; j<size; ++j)
				for (int i=0; i<size; ++i)
					mc[j]=min(mc[j], matrix[i][j]-mr[i]);
			int counter=0;
			while (counter<size){
				int k=0;
				for (int i=0; i<size; ++i)
					if ((xy[i]==-1) && findOus(i))
						++k;
				counter+=k;
				if (k==0) {
					//////////////////
					int z=Integer.MAX_VALUE;
					for (int i=0; i<size; ++i){
						if (vx[i])
							for (int j=0; j<size; ++j){
								if (!vy[j])
									z=min(z, matrix[i][j]-mr[i]-mc[j]);
							}
					}
					for (int i=0; i<size; ++i) {
						if (vx[i]){
							mr[i]+=z;
						}
						if (vy[i]){
							mc[i]-=z;
						}
					///////////////////
					}
				}
			}

			answer=0;
			for (int i=0; i<size; ++i){
				answer+=matrix[i][xy[i]];

			}
		}


		public void print()throws IOException{
			PrintWriter out;
			out=new PrintWriter(new FileWriter("assignment.out"));
			kuhn();
			out.print(answer+"\n");
			for (int i=0; i<size; ++i){
				out.print((i+1)+" "+(xy[i]+1));
				if (i!=size-1)
					out.print("\n");
			}
			out.flush();
			out.close();
		}
	}


	/////////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////////

	public static void main(String[] arg)throws IOException{
		Matrix g=new bugs.Matrix();
		g.loadGraph();
		g.print();
	}
}