Program Kruskal;

type vecini=record
        x,y,cost:longint;
     end;

var f,g:text;
    t:array[1..200000] of longint;
    a:array[1..400000] of vecini;
    b:array[1..200000] of vecini;
    aux:vecini;
    Cost_Total,i,j,n,m:longint;

procedure qsort(l,r:longint);
 var i,j:longint;
     pivot:vecini;

 begin
   i:=l; j:=r; pivot:=a[random(r-l)+l];
   repeat
        while a[i].cost<pivot.cost do i:=i+1;
        while pivot.cost<a[j].cost do j:=j-1;
        if i<=j then begin
                aux:=a[i];
                a[i]:=a[j];
                a[j]:=aux;
                i:=i+1; j:=j-1;
        end;
   until i>j;
   if i<r then qsort(i,r);
   if l<j then qsort(l,j);
 end;


function radacina(nod:longint):longint;
 var r:longint;
 begin
        if t[nod]=nod then
                r:=nod
        else
                r:=radacina(t[nod]);
        t[nod]:=r;
        radacina:=r;
 end;


begin
 assign(f,'apm.in'); reset(f);
 assign(g,'apm.out'); rewrite(g);
 read(f,n,m);
 for i:=1 to m do
        read(f,a[i].x,a[i].y,a[i].cost);
 qsort(1,m);
 for i:=1 to n do
        t[i]:=i;
 j:=1; Cost_Total:=0;
 for i:=1 to n-1 do begin
        while radacina(a[j].x)=radacina(a[j].y) do
                j:=j+1;
        t[radacina(a[j].x)]:=radacina(a[j].y);
        Cost_Total:=Cost_Total+a[j].cost;
        b[i]:=a[j];
 end;
 writeln(g,Cost_Total);
 writeln(g,n-1);
 for i:=1 to n-1 do
        writeln(g,b[i].x,' ',b[i].y);
 close(f); close(g);
end.