type date=record ai,aj,ax:longint end;
var t,v:array[1..200005] of date;
    TT,RG:array[1..400005] of longint;
    n,m,i,j,x,total,a,b:longint;
    aux:date;

 function radacina(k:longint):longint;
  begin
   while TT[k]<>k do k:=TT[k];
   radacina:=k
  end;

 procedure unire(a,b:longint);
  begin
   if RG[a]<RG[b] then TT[a]:=b;
   if RG[a]>RG[b] then TT[b]:=a;
   if RG[a]=RG[b] then
    begin
     TT[a]:=b;
     inc(RG[b])
    end;
  end;

begin
assign(input,'apm.in'); reset(input);
assign(output,'apm.out'); rewrite(output);
readln(n,m);
for i:=1 to m do readln(t[i].ai,t[i].aj,t[i].ax);
for i:=1 to m-1 do
 for j:=1 to m-i do
  if t[j].ax>t[j+1].ax then
   begin
    aux:=t[j];
    t[j]:=t[j+1];
    t[j+1]:=aux
   end;
for i:=1 to n do
 begin
  TT[i]:=i;
  RG[i]:=1
 end;
i:=0;
while (x<>n-1) and (i<m) do
 begin
  inc(i);
  a:=radacina(t[i].ai);
  b:=radacina(t[i].aj);
  if a<>b then
   begin
    unire(a,b);
    inc(x);
    v[x].ai:=t[i].ai;
    v[x].aj:=t[i].aj;
    inc(total,t[i].ax)
   end;
 end;
writeln(total);
writeln(x);
for i:=1 to x do writeln(v[i].aj,' ',v[i].ai);
close(input);
close(output)
end.