{
TASK: TINKLAS
LANG: PASCAL
}
{
Uždavinio sprendimo ideja:
na mums šiaip ar taip reikes sujungti tarpusavy visus komutatorius.
Taigi tarp ju tures reikes surasti minimalu jungiamaji medi. Taigi uždavinys
suskaidomas i dvi dalis:
1. Triviali dalis: reikia prijungti kompiuterius prie komutatoriu. Kiekvienam
kompiuteriui surandam artimiausia komutatoriu. Ta galima padaryti nuskaitant
duomenis.
2. Pasinaudojant kokiu nors algoritmu minimaliam jungiamajam medžiui rasti
surezgame tinkla tarp komutatoriu. Aš naudojau Prim'o algoritma, kai eile
realizuojama heap struktura.

}
program don;

const
  maxkomp = 1000;
  maxkomut = 1000;
  maxkaina = 1000;

type
  TJungimas =
    record
      kaina : longint;
      kaimynas : longint;
    end;

  THeap =
    record
      ilgis : longint;
      info : array [1..maxkomut] of longint;
    end;


var
  atstumas : array[1..maxkomut] of longint;
  map : array[1..maxkomut] of longint;

{išima iš heap'o Q mažiausia elementa ir gražina ji kaip funkcijos rezultata}
function maziausias(var Q: THeap) : longint;

  {heapify yra veiksmas kuriuo atstatoma sunaikinta heap'o struktura}
  procedure heapify(i : longint);
  var
    l, r, smallest, tmp : longint;
  begin
    l := i * 2;
    r := i * 2 + 1;
    if (l <= Q.ilgis) and (atstumas[Q.info[l]]<atstumas[Q.info[i]])
         then smallest := l
         else smallest := i;
    if (r <= Q.ilgis) and (atstumas[Q.info[r]]<atstumas[Q.info[smallest]])
         then smallest := r;
    if smallest <> i then
    begin
      tmp := Q.info[i];
      Q.info[i] := Q.info[smallest];
      map[Q.info[smallest]] := i;
      Q.info[smallest] := tmp;
      map[tmp] := smallest;
      heapify(smallest);
    end;
  end;

var
  rez : longint;

begin
  rez := Q.info[1];
  Q.info[1] := Q.info[Q.ilgis];
  map[Q.info[1]] := 1;
  Q.ilgis := Q.ilgis - 1;
  heapify(1);
  maziausias := rez;
//  writeln('Extracted ',atstumas[rez], ' ', rez);
end;

{pakitus i-tojo elemento atstumas[] reikšmei reikia pertvarkyti eile taip,
kad ji tenkintu heap'ui keliamus reikalavimus}

procedure atnaujink(var Q:Theap; i : longint);
var
  tmp : longint;
begin
  while (i <> 1) and (atstumas[q.info[i]] < atstumas[q.info[i div 2]]) do
  begin
    tmp := q.info[i];
    q.info[i] := q.info[i div 2];
    map[q.info[i div 2]] := i;
    q.info[i div 2] := tmp;
    map[tmp] := i div 2;
    i := i div 2;
  end;
end;

var
  f : text;
  k : longint; {kiek kompiuteriu}
  m : longint; {kiek komutatoriu}
  i, j : longint; {ciklu valdymui}
  nrm, nrk, nr1, nr2, u : longint; {komutatoriaus ir kompiuterio numeriams}
  kaina, visakaina : longint;
  kompkainos : array [1..maxkomp] of TJungimas;
  komkainos : array [1..maxkomut, 1..maxkomut] of longint;
  eileje : array [1..maxkomut] of boolean;
  eile : THeap;
  tevas : array[1..maxkomut] of longint;
  ats : array[1..maxkomut] of longint;
begin
  visakaina := 0;
  for i := 1 to maxkomp do kompkainos[i].kaina := maxkaina + 1;

  assign(f, 'TINKLAS.DAT');
  reset(f);
  readln(f, k, m);

  {skaitom kompiureriu sujungimo su komutatoriais kainas ir iskarto pasizymim
  pigiausius kiekvieno kompiuterio sujungimo su kuriuo nors komutatorium variantus}
  for i := 1 to k * m do
  begin
    readln(f, nrk, nrm  , kaina);
    if kompkainos[nrk].kaina > kaina then
    begin
      kompkainos[nrk].kaina := kaina;
      kompkainos[nrk].kaimynas := nrm;
    end;
  end;
  for i := 1 to k do inc(visakaina, kompkainos[i].kaina);


  {skaitom komutatoriu tarpusavio sujungimo kainas}
  for i := 1 to m*(m-1) div 2 do
  begin
    readln(f, nr1, nr2, kaina);
    komkainos[nr1, nr2] := kaina;
    komkainos[nr2, nr1] := kaina;
  end;

  close(f);

  fillchar(eileje, sizeof(eileje), true);
  for i := 1 to m do atstumas[i] := maxkaina + 1;
  atstumas[1] := 0;
  Tevas[1] := -1;
  eile.ilgis := m;
  for i := 1 to m do eile.info[i] := i;
  for i := 1 to m do map[i] := i;
  for j := 1 to m do   {reikia itraukti lygiai m virsuniu} {PRIM}
  begin
    u := maziausias(eile);
    visakaina := visakaina + atstumas[u];
    ats[j] := u;
    eileje[u] := false;
    for i := 1 to m do if i <> u then
    begin
      if eileje[i] and (komkainos[i, u] < atstumas[i]) then
      begin
        Tevas[i] := u;
        atstumas[i] := komkainos[i, u];
        atnaujink(eile, map[i]);
      end;
    end;
  end;

  assign(f, 'TINKLAS.REZ');
  rewrite(f);
  writeln(f, visakaina,' ', m - 1 + k);
  for i := 2 to m do
  begin
    writeln(f, 'M ',ats[i], ' M ',tevas[ats[i]]);
  end;

  for i := 1 to k do
  begin
    writeln(f, 'M ',kompkainos[i].kaimynas, ' K ',i);
  end;

  close(f);

end.