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

in C#: Michael Gärtner
************************************************/

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Logofatu
{
    public class P04SpanningTree
    {
        public static String FileInputName = "kruskal.in";
        public static String FileOutputName = "kruskal.out";
        public static IFormatProvider formatProvider = System.Globalization.CultureInfo.GetCultureInfo("en-US").NumberFormat;
        
        static void Main(string[] args)
        {
            StreamReader sr = null;
            StreamWriter sw = null;
            try
            {
                sr = new StreamReader(FileInputName);
                sw = new StreamWriter(FileOutputName);

                int n = int.Parse(sr.ReadLine());
                SortedDictionary<double,List<int>> E = 
                    new SortedDictionary<double,List<int>>();
                for ( int i = 0; i < n; i++ )
                {
                    string[] sArray = sr.ReadLine().Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries);
                    for ( int j = 0; j < n; j++ )
                    {    
                        double aux = double.Parse(sArray[j],formatProvider);
                        if ( i < j && aux != 0)
                        {
                            putInMultimap(E, aux, i * n + j);
                        }
                    }
                }
                
                int[] C = new int[n];
                for ( int i = 0; i < n; i++ )
                {
                    C[i] = i;
                }

                SortedDictionary<double, List<int>> H = new SortedDictionary<double, List<int>>();                

                int szH = 0; 
                while ( szH < n - 1 )
                {
                    TreeMultimapIterator it = new TreeMultimapIterator(E);
                    it.next();
                    int uu = it.Value / n;
                    int vv = it.Value % n;
                    while ( C[uu] == C[vv] )
                    {
                        it.next();
                        uu = it.Value / n;
                        vv = it.Value % 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 ( int i = 0; i < n; i++ )
                    {
                        if ( C[i] == ma )
                        {
                            C[i] = mi;
                        }
                    }                   
                }
                double cost = 0;
                foreach ( var entry in H )
                {
                    List<int> values = entry.Value;
                    double key = entry.Key;
                    foreach ( var value in values )
                    {
                        sw.Write("({0}, {1}) -> ",
                        (value / n + 1).ToString("D",formatProvider),
                        (value % n + 1).ToString("D",formatProvider));
                        sw.WriteLine("{0}",key.ToString("F1",formatProvider));
                        cost += key;
                    }
                }
                sw.WriteLine("--------------------");
                sw.WriteLine("Gewicht : {0}",cost.ToString("F1",formatProvider));                 
            }
            catch ( IOException ex )
            {                
                Console.WriteLine("Fehler bei der Dateiverarbeitung!\n\n" + ex);
                Console.ReadLine();
            }
            finally
            {
                if ( sr != null )
                {
                    sr.Close();
                }
                if ( sw != null )
                {
                    sw.Close();
                }
            }
        }

        private static void putInMultimap(SortedDictionary<double, List<int>> mmap, double key, int value)
        {
            List<int> values = null;
            if ( !mmap.TryGetValue(key, out values) )
            {
                values = new List<int>();
                mmap.Add(key, values);
            }
            values.Add(value);
        }

        private class TreeMultimapIterator
        {
            private SortedDictionary<double, List<int>>.Enumerator mmapIt;
            private List<int>.Enumerator currValueIt;
            private int currValue;
            private KeyValuePair<double, List<int>> currEntry;
            private SortedDictionary<double, List<int>> mmap;

            public TreeMultimapIterator(SortedDictionary<double, List<int>> mmap)
            {
                this.mmap = mmap;
                this.mmapIt = mmap.GetEnumerator();
                mmapIt.MoveNext();
                this.currEntry = this.mmapIt.Current;
                this.currValueIt = this.currEntry.Value.GetEnumerator();
            }

            public bool next()
            {
                if ( this.currValueIt.MoveNext() )
                {
                    this.currValue = this.currValueIt.Current;
                    return true;
                }
                else
                {
                    if ( mmapIt.MoveNext() )
                    {
                        this.currEntry = this.mmapIt.Current;
                        this.currValueIt = this.currEntry.Value.GetEnumerator();
                        if ( this.currValueIt.MoveNext() )
                        {
                            this.currValue = this.currValueIt.Current;
                            return true;
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
            }

            public double Key { get { return this.currEntry.Key; } }

            public int Value { get { return this.currValue; } }

            public void remove()
            {
                this.currEntry.Value.Remove(currValue);
                if ( this.currEntry.Value.Count == 0 )
                {
                    this.mmap.Remove(mmapIt.Current.Key);
                }
            }
        }    
        
    }
}