package net.mrpaul.XA270.greedy;

import java.io.*;
import java.util.*;

public class Kruskals {
	private static final Comparator<List<Integer>> C = new Comparator<List<Integer>>() {
	    public int compare(List<Integer> pList1, List<Integer> pList2) {
	        return pList1.get(0).compareTo(pList2.get(0));
	    }
	};

	public static void main(String args[]) throws IOException {
		kruskals("in.txt");
	}

	public static void kruskals(String fileName) throws IOException {
		Scanner scan = new Scanner(new File(fileName));
		int n = Integer.parseInt(scan.nextLine());
		StringTokenizer tokenizer;

		List<List<Integer>> Q = new ArrayList<List<Integer>>();
		List<List<Integer>> E = new ArrayList<List<Integer>>();
		int token;
		List<Integer> e;
		for (int i=0; i<n; i++) {
			Q.add(new ArrayList<Integer>());
			tokenizer = new StringTokenizer(scan.nextLine());
			for (int j=0; j<n; j++) {
				token = Integer.parseInt(tokenizer.nextToken());
				Q.get(i).add(token);
				if (token != -1) {
					e = new ArrayList<Integer>();
					e.add(token);
					e.add(i);
					e.add(j);
					E.add(e);
				}
			}
		}
		Collections.sort(E, C);

		UF U = new UF(n);

		List<List<Integer>> O = new ArrayList<List<Integer>>();
		for (int i=0; i<n; i++) {
			O.add(new ArrayList<Integer>());
			for (int j=0; j<n; j++) {
				O.get(i).add(-1);
			}
		}

		int s;
		int f;
		int sum = 0;
		while (U.count() > 1) {
			e = E.get(0);
			E.remove(0);
			s = e.get(1);
			f = e.get(2);
			if (!U.connected(s, f)) {
				U.union(s, f);
				O.get(s).set(f, e.get(0));
				O.get(f).set(s, e.get(0));
				sum += e.get(0);
			}
		}

		String o = "";
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				o += O.get(i).get(j)+" ";
			}
			o += "\n";
		}
		o += sum;

		BufferedWriter out = new BufferedWriter(new FileWriter("out.txt"));
		out.write(o);
		out.close();
	}
}