//Kruskal
//100p Infoarena
program kruskal;
type much=record
     x,y,c:longint;
     end;
     vector=array[1..200000]of longint;
     vect2=array[0..1,1..400001]of longint;
     vect=array[1..400001]of much;
var muchie:vect;
    sol:vect2;
    n,m,nrmuchii,costtotal,k,i,j,cost:longint;
    t,h:vector;
    f,g:Text;
    intrare,iesire:array[1..500000]of char;

procedure citire;
var i:longint;
begin
readln(f,n,m);
for i:=1 to m do readln(f,muchie[i].x,muchie[i].y,muchie[i].c);
end;


procedure swap(var a,b:much);
var aux:much;
begin
aux:=a; a:=b; b:=aux;
end;

procedure qsort(var v:vect; st,dr:longint);
var i,j:longint;   pivot:much;
begin
i:=st;
j:=dr;
pivot:=v[(st+dr) div 2];
while i<=j do begin
              while v[i].c<pivot.c do inc(i);
              while v[j].c>pivot.c do dec(j);
              if i<=j then begin
                           swap(v[i],v[j]);
                           inc(i);
                           dec(j);
                           end;
              end;
if st<j then qsort(v,st,j);
if i<dr then qsort(v,i,dr);
end;


procedure init_multimi_disjuncte;
var i:longint;
begin
for i:=1 to n do
                begin
                t[i]:=i;  //radacina arborelui e propriul parinte
                h[i]:=0;  //initial fiecare arbore va contine un singur nod
                end;
end;

function multime(nod:longint):longint;
begin
if nod<>t[nod] then t[nod]:=multime(t[nod]);
multime:=t[nod];
end;

procedure reuneste(i,j:longint);
begin
i:=multime(i); j:=multime(j);
if i<>j then
            begin
            if h[i]>h[j] then t[j]:=i else t[i]:=j;
            if h[i]=h[j] then h[j]:=h[j]+1;
            end;
end;


begin
assign(f,'apm.in'); reset(f);   settextbuf(f,intrare);
assign(g,'apm.out');rewrite(g); settextbuf(g,iesire);
citire;
qsort(muchie,1,m);
init_multimi_disjuncte;
nrmuchii:=0; //am adaugat 0 muchii in apm deocamdata
costtotal:=0;
for k:=1 to m do
  begin
  with muchie[k] do
                   begin
                   i:=x; j:=y; cost:=c;
                   end;
  if multime(i)<>multime(j) then //daca nodurile nu fac parte din
                                begin //acelasi arbore, se "reunesc" multimile
                                reuneste(i,j);
                                costtotal:=costtotal+cost; //costul total al apmului
                                inc(nrmuchii); //am adaugat o muchie in apm
                                sol[0,nrmuchii]:=i;
                                sol[1,nrmuchii]:=j;
                                end;
  end;
writeln(g,costtotal);
writeln(g,nrmuchii);
for i:=1 to nrmuchii do writeln(g,sol[0,i],' ',sol[1,i]);
close(f); close(g);
end.