{                    SPRENDIMO ID¸JA

  ¾is uØdavinys susiveda Ô minimalaus grafo karkaso radimÐ. Grafo
virÕ×nÓs Ñia yra miestai, o briaunas atstoja keliai. Grafo
karkasas - tai medis, kurio virÕ×nÓs yra grafo virÕ×nÓs, o briaunÖ
yra viena maØiau nei grafo virÕ×niÖ. Karkaso briaunos yra grafo
briaunÖ poaibis. Minimalus grafo karkasas - tai karkasas, kurio
briaunÖ svoris (Õiuo atveju kelio ilgis) maØiausias.
  ¾iam uØdaviniui sprÒsti tinka godus algoritmas.
  Imame bet kuriÐ grafo virÕ×nÒ. Nuo jos pradÓsime ieÕkoti karkaso.
Randame tos virÕ×nÓs kaimynus - miestus Ô kuriuos galima patekti
tiesiogiai. IÕ jÖ iÕrenkame tÐ, iki kurio atstumas yra maØiausias.
¾Ô miestÐ ir briaunÐ iki pradinio miesto Ôtraukiame Ô karkasÐ. Tada
ÔtrauktÐ miestÐ paÕaliname iÕ kaimynÖ sÐraÕo ir Ôtraukiame naujus
kaimynus, kurie pasiekiami iÕ naujai ÔraÕyto Ô karkasÐ miesto. Tada
vÓl tarp visÖ kaimynÖ ieÕkome tokio, kuriam iki kurio nors karkase
esanÑio miesto yra trumpiausias atstumas. ½traukiame Ô karkasÐ miestÐ
ir trumpiausiÐ briaunÐ iki karkaso, ir vÓl karojame apraÕytus veiksmus,
kol nebelieka miestÖ, kuriuos reikÓtÖ prijungti.
}


{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 65000,0,655360}

program Fantazija;
  const max_miest = 170; {Maksimalus miestÖ skaiÑius}

  var atstumai : array[1..max_miest, 1..max_miest] of integer;
      { AtstumÖ tarp miestÖ matrica }

      buvo,   { Miestai, kurie jau yra sujungti (karkase)}
      kaimynai : array[1..max_miest]of byte;
       {Karkaso kaimynai - miestai Ô kuriuos tiesiogiai galima
        nueiti iÕ Ô karkasÐ ÔtrauktÖ miestÖ}

      kiek,          {Kiek yra miestÖ}
      kiek_b,        {Kiek elementÖ yra masyve buvo}
      kiek_k : byte; {Kiek elementÖ yra masyve kaimynai}

      karkasas : array[1..max_miest]of record  {Rasti keliai}
                                          m1, m2 : byte
                                        end;

      rasta : byte; {Kiek jau rasta keliÖ, kuriuos reikia nuvalyti}
      rezult : longint;

  procedure duomenys;
  { Proced×ra perskaito pradinius duomenis }
    var t : text;
        i, j : byte;
  begin
    Assign(t,'miestai.dat');  Reset(t);
    readln(t, kiek);
    for i := 1 to kiek do begin
      for j := 1 to kiek do read(t,atstumai[i,j]);
      readln(t)
    end;
    Close(t)
  end;

  procedure paieska;
    { PagrindinÓ keliÖ radimo proced×ra }
    var i, j, v1, v2 : byte;
        min : integer;

    procedure pradzia;
      {Priskiriamos pradinÓs kintamÖjÖ reikÕmÓs}
      var i : byte;
    begin
      buvo[1]:=1; kiek_b := 1; {PradÓsime nuo pirmojo miesto}
      kiek_k := 0;
      for i := 1 to kiek do    {Rasime pirmojo miesto kaimynus - }
        if atstumai[1,i]<>0    {miestus Ô kuriuos iÕ jo galima patekti}
          then begin           {tiesiogiai}
                 inc(kiek_k);
                 kaimynai[kiek_k]:=i
               end;
      rasta := 0;
    end;

    procedure nauji_kaim;
    { Pakoreguojamas karkaso kaimynÖ sÐraÕas }
      var i : byte;
    begin
      for i := 1 to kiek do  { Ôtrauksime naujus kaimynus }
        if atstumai[kaimynai[v2],i]<>0
          then begin
                 j := 1;
                 while j<=kiek_k do begin  {Ar i-asis miestas jau}
                   if kaimynai[j]=i then break; {kaimynÖ sÐraÕe?}
                   inc(j)
                 end;
                 if j>kiek_k
                   then begin
                          j := 1;
                          while j<=kiek_b do begin { Ar i-asis jau }
                            if buvo[j]=i then break; {karkase?}
                            inc(j)
                          end;
                          if j > kiek_b   {½traukiama naujÐ miestÐ}
                            then begin    {jei jis niekur kitur }
                                   inc(kiek_k); {nebuvo ÔraÕytas}
                                   kaimynai[kiek_k]:=i
                                 end
                        end
               end;
      dec(kiek_k); {IÕmesime miestÐ, kuris ÔraÕytas elemente v2}
      if v2 <> max_miest
        then Move(kaimynai[v2+1],kaimynai[v2], kiek_k-v2+1);
    end;

  begin
    pradzia;
    rezult := 0;
    while kiek_k<>0 do  { Kol dar yra neprijungtÖ miestÖ... }
      begin
        min := maxint;
        for i := 1 to kiek_b do   {rasime miestÐ iÕ karkaso ir miestÐ}
          for j := 1 to kiek_k do {iÕ kaimynÖ, tarp kuriÖ tiesioginis }
            if (atstumai[buvo[i],kaimynai[j]]<min)and {atstumas}
               (atstumai[buvo[i],kaimynai[j]]<>0)     {minimalus}
            then begin
                   min := atstumai[buvo[i],kaimynai[j]];
                   v1 := i;
                   v2 := j
                 end;

        inc(kiek_b);   {½traukiame naujÐ miestÐ Ô karkasÐ}
        buvo[kiek_b]:=kaimynai[v2];

        inc(rasta);    {½traukiame naujÐ keliÐ Ô karkasÐ}
        karkasas[rasta].m1 := kaimynai[v2];
        karkasas[rasta].m2 := buvo[v1];
        inc(rezult,atstumai[kaimynai[v2], buvo[v1]]);

        nauji_kaim;

      end;
  end;

  procedure atsakymas;
  {Proced×ra ÔraÕo rezultatÐ}
    var t :text;
        i : integer;
  begin
    Assign(t, 'miestai.rez'); rewrite(t);
    writeln(t, rezult);
    for i := 1 to rasta do
      writeln(t, karkasas[i].m1, ' ', karkasas[i].m2);
    close(t);
  end;

begin
  duomenys;
  paieska;
  atsakymas
end.