type muchie=record
            x,y,c:longint;
            end;

var t,nv:array[1..200000] of longint;
    mu,f:array[1..400000] of muchie;
    n,m:longint;
    s:int64;

procedure citire;
var i:longint;
begin
assign(input,'apm.in');reset(input);
readln(n,m);
for i:=1 to m do
readln(mu[i].x,mu[i].y,mu[i].c);
close(input);
end;

procedure qsort(l,r:longint);
var i,j,x:longint;
    y:muchie;
begin
i:=l;j:=r;x:=mu[(l+r) div 2].c;
 repeat
 while mu[i].c<x do inc(i);
 while x<mu[j].c do dec(j);
 if i<=j then
   begin
   y:=mu[i];mu[i]:=mu[j]; mu[j]:=y; inc(i); dec(j);
   end;
 until i>=j;

 if l<j then qsort(l,j);
 if i<r then qsort(i,r);
end;


function cauta(x:longint):longint;
var r,y,q:longint;
begin
r:=x;
while t[r]<>0 do r:=t[r];
cauta:=r;
y:=x;
while t[y]<>0 do begin
    q:=t[y];
    t[y]:=r;
    y:=q;
    end;
end;


procedure unif(x,y:longint);
begin
if nv[x]>nv[y] then t[y]:=x
    else t[x]:=y;
  if nv[x]=nv[y] then inc(nv[y]);
end;

procedure kruskal;
var i,nr,o,u:longint;
begin
assign(output,'apm.out');rewrite(output);
nr:=0;         i:=1;
while (nr<n-1)  do
 begin
 o:=cauta(mu[i].x);
 u:=cauta(mu[i].y);
 if o<>u then begin
              f[nr+1]:=mu[i];
              s:=s+mu[i].c;
              unif(o,u);
              inc(nr);
              end;
 inc(i)
 end;
end;

procedure afisare;
var i:longint;
begin
writeln(s);
writeln(n-1);
for i:=1 to n-1 do
writeln(f[i].x,' ',f[i].y);
close(output);
end;

begin
citire;
qsort(1,m);
kruskal;
afisare;
end.