/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

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

public class P04SpanningTree {
  private static final String FileInputName = "kruskal.in";
  private static final String FileOutputName = "kruskal.out";

  public static void main(String[] args) throws IOException {
    Scanner scanner = null;
    PrintStream out = null;
    try {
      scanner = new Scanner(new File(FileInputName)).useLocale(Locale.ENGLISH);
      out = new PrintStream(new File(FileOutputName));
      int n = scanner.nextInt();
      TreeMap<Double, List<Integer>> E = new TreeMap<Double, List<Integer>>();
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          if (!scanner.hasNextDouble())
            return;
          double aux = scanner.nextDouble();
          if (i < j && aux != 0D) {
            putInMultimap(E, aux, i * n + j);
          }
        }
      }
      int C[] = new int[n];
      for (int i = 0; i < n; i++)
        C[i] = i;
      TreeMap<Double, List<Integer>> H = new TreeMap<Double, List<Integer>>();
      int szH = 0;
      while (szH < n - 1) {
        TreeMultimapIterator it = new TreeMultimapIterator(E);
        it.next();
        int uu = it.value().intValue() / n;
        int vv = it.value().intValue() % n;
        while (C[uu] == C[vv]) {
          it.next();
          uu = it.value().intValue() / n;
          vv = it.value().intValue() % n;
        }
        putInMultimap(H, it.key(), it.value());
        szH++;
        it.remove();
        int mi = Math.min(C[uu], C[vv]);
        int ma = Math.max(C[uu], C[vv]);
        for (short i = 0; i < n; i++)
          if (C[i] == ma)
            C[i] = mi;
      }
      double cost = 0;
      Set<Map.Entry<Double, List<Integer>>> hEntries = H.entrySet();
      for (Map.Entry<Double, List<Integer>> entry : hEntries) {
        List<Integer> values = entry.getValue();
        double key = entry.getKey();
        for (int value : values) {
          out.printf("(%d, %d) -> ", value / n + 1, value % n + 1);
          out.println(key);
          cost += key;
        }
      }
      out.println("--------------------");
      out.println("Cost: " + cost);

    } finally {
      if (scanner != null) {
        scanner.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }

  private static void putInMultimap(TreeMap<Double, List<Integer>> mmap,
      Double key, Integer value) {
    List<Integer> values = mmap.get(key);
    if (values == null) {
      values = new ArrayList<Integer>();
      mmap.put(key, values);
    }
    values.add(value);
  }

  private static class TreeMultimapIterator {
    private Iterator<Map.Entry<Double, List<Integer>>> mmapIt;
    private ListIterator<Integer> currValuesIt;
    private Integer currValue;

    Map.Entry<Double, List<Integer>> currEntry;

    TreeMultimapIterator(TreeMap<Double, List<Integer>> mmap) {
      this.mmapIt = mmap.entrySet().iterator();
    }

    boolean next() {
      if (this.currValuesIt != null && this.currValuesIt.hasNext()) {
        this.currValue = this.currValuesIt.next();
        return true;
      } else if (mmapIt.hasNext()) {
        this.currEntry = this.mmapIt.next();
        this.currValuesIt = this.currEntry.getValue().listIterator();
        this.currValue = this.currValuesIt.next();
        return true;
      } else {
        return false;
      }
    }

    Double key() {
      return this.currEntry.getKey();
    }

    Integer value() {
      return this.currValue;
    }

    void remove() {
      this.currValuesIt.remove();
      if (this.currEntry.getValue().isEmpty()) {
        this.currValuesIt = null;
        this.mmapIt.remove();
      }
    }
  }
}