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

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 quick(s,d:longint);
var a,b,ai:longint;
begin
a:=s; b:=d;
repeat
while muchie[a].c<muchie[b].c do dec(b);
swap(muchie[a],muchie[b]); inc(A); ai:=1;
if a<b then
            begin
            while muchie[a].c<muchie[b].c do inc(A);
            if a<b then
                       begin
                       swap(muchie[a], muchie[b]);
                       dec(b); ai:=0;
                       end;
            end;
until b<=a;
if s<a-ai then quick(s,a-ai);
if a-ai+1<d then quick(a-ai+1,d);
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;
quick(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.