import java.text.DecimalFormat;
import java.util.*;
public class Main{
	static double Max=-1;
	static int[] vis,res;
	static int n;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        vis = new int[n];
        res = new int[n];
        double[][] s = new double[n][n];
        for(int i=0;i<n;i++)
        	for(int j=0;j<n;j++)
        		s[i][j]=sc.nextDouble();
        int[] re = new int[n];
        find(s,0,0,re);
        DecimalFormat sf = new DecimalFormat("#0.00");
        int tp = (int)Max;
        System.out.println(sf.format(Max));
        for(int i=0;i<n;i++)
        	System.out.println((i+1)+" "+(res[i]+1));
    }
    static void find(double[][] s,double max,int t,int[] re){
    	if(t==n){
    		if(max>Max){
    			for(int i=0;i<n;i++){
    				res[i]=re[i];
    			}
    			Max=max;
    		}
    		return ;
    	}
    	for(int i=0;i<n;i++){
    		if(vis[i]!=1){
    			vis[i]=1;
    			re[t]=i;
    			find(s,max+s[t][i],t+1,re);
    			vis[i]=0;
    		}
    	}
    }
}