{
TASK: TINKLAS
LANG: PASCAL
}

program tinklai;
  const PR = 'TINKLAS.DAT';
        RZ = 'TINKLAS.REZ';
        MAX = 1000;
  type Tvmas = array [1..2*MAX] of longint;
       Tdmas = array [1..MAX, 1..MAX] of longint;
       Tirasas = record
                   kt1, kt2, kaina: longint;
                 end;
       Tsar = array [1..MAX*MAX] of Tirasas;
  { globalieji kintamieji }
  var K, M: longint;
      kp_kt: Tdmas;
      sar: Tsar;
      mkaina: longint;
{*****************************************************************}
  procedure quicksort(var a: Tsar; Lo,Hi: longint);
     procedure sort(l,r: longint);
       var i,j,x: longint;
           t: Tirasas;
    begin
      i:=l; j:=r; x:=a[(l+r) DIV 2].kaina;
      repeat
        while a[i].kaina<x do i:=i+1;
        while x<a[j].kaina do j:=j-1;
          if i<=j then
             begin
              t:=a[i]; a[i]:=a[j]; a[j]:=t;
              i:=i+1; j:=j-1;
            end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
   end;

  begin {quicksort};
    sort(Lo,Hi);
  end;

{*****************************************************************}
  { darbas su aibemis }
  var p, rank: Tvmas; { globalusis - pointeriai }


  procedure Make_set (x: longint);
  begin
    p[x] := x;
    rank[x] := 0;
  end;

  function Find_set (x: longint): longint;
  begin
    if x <> p[x]
       then p[x] := Find_set (p[x]);
    Find_set := p[x];
  end; { find_set }

  procedure Link (x, y: longint);
  begin
    if rank[x] > rank[y]
       then p[y] := x
       else begin
              p[x] := y;
              if rank[x] = rank[y]
                 then rank[y] := rank[y] + 1;
            end;
  end;

  procedure union (x, y: longint);
  begin
    Link (Find_set(x), Find_set(y));
  end;
{*****************************************************************}

  procedure jungti_komut (var jungk: Tvmas);
    { sujingiami Komutatoriai - Kruskalo algoritmas }
    var MM, i, kt1, kt2, ind: longint;
  begin
    MM := M * (M-1) div 2;
    Quicksort (sar, 1, MM);
    { inicializuoti aibes }
    for i := 1 to M do
      Make_set (i);
    ind := 0;
    for i := 1 to MM do
      begin
        kt1 := sar[i].kt1; kt2 := sar[i].kt2;
        if  Find_set (kt1) <> Find_set (kt2)
            then begin { radome jungti }
                  ind := ind + 1;
                  jungk[ind] := i;
                  union(kt1, kt2);
                  mkaina := mkaina + sar[i].kaina;
              end;
      end;
  end; { jungti_komut }

  procedure jungti_komp (var jungk: Tvmas);
    var kp, kt: longint;
  begin
    for kp := 1 to K do
      jungk[kp] := 1;
    for kp := 1 to K do
      for kt := 2 to M do
        if kp_kt[kp, jungk[kp]] > kp_kt[kp, kt]
           then jungk[kp] := kt;
  end; { jungti_komp }

  procedure jungti (var mkaina, L : longint; var jungk, jungm: Tvmas);
    var i: longint;
  begin
    L := K + M - 1; { reikiamų laidų skaičius }
    { prijungiame kompiuterius ir apskaičiuojame kainą }
    jungti_komp (jungk);
    mkaina := 0;
    for i := 1 to K do
      mkaina := mkaina + kp_kt[i, jungk[i]];
    { sungiame komutatorius ir apskaiciuojame kaina }
    if M > 1 then jungti_komut (jungm);
  end; { jungti }

  procedure skaityti (var K, M: longint; var kmp_kmt: Tdmas; var sar: Tsar);
    var f: text;
        IKI, i, kmp, kmt, kmt1, kmt2, kaina: longint;
  begin
    assign (f, PR);
    reset (f);
    readln (f, K, M);
    IKI := K*M;
    for i := 1 to iki do
      begin
        readln (f, kmp, kmt, kaina);
        kmp_kmt[kmp, kmt] := kaina;
      end;
    for i := 1 to M*(M-1) div 2 do
        readln (f, sar[i].kt1, sar[i].kt2, sar[i].kaina);
   close (f);
  end; { skaityti }

  procedure rasyti (min_kaina, L: longint; jungk, jungm: Tvmas);
    var f: text;
        i: longint;
  begin
    assign (f, RZ);
    rewrite (f);
    writeln (f, min_kaina, ' ', L);
    for i := 1 to K do
      writeln (f, 'K ', i, ' M ', jungk[i]);
    for i := 1 to M-1 do
       writeln (f, 'M ', sar[jungm[i]].kt1, ' M ',sar[jungm[i]].kt2);
    close (f);
  end; { rašyti }

  var L: longint;
     jungk, jungm: Tvmas;
begin
  skaityti (K, M, kp_kt, sar);
  jungti (mkaina, L, jungk, jungm);
  rasyti (mkaina, L, jungk, jungm);
end.