program dsdl;
type mi=record
x,y,c:longint;
end;
var f,g:text;
n,i,j,suma,k,m,a,b,di,dj,aux2:longint;
ok:boolean;
aux:mi;
v:array[1..400022] of mi;
nr,t:array[1..400022] of longint;
function tata(nod:longint):longint;
begin
if t[nod]<0 then
tata:=nod
else
begin
t[nod]:=tata(t[nod]);
tata:=t[nod];
end;
{ if t[nod]<>0 then
21.
t[nod]:=tata(t[nod])
22.
else
23.
tata:=nod;  }
end;
procedure sortare;
begin
repeat
ok:=true;
for i:=1 to m-1 do
if v[i].c>v[i+1].c then
begin
aux:=v[i];
v[i]:=v[i+1];
v[i+1]:=aux;
ok:=false;
end;
until ok;
end;
function pivot(st,sf:longint):longint;
  begin
   i:=st;
   j:=sf;
   di:=0;
   dj:=1;
     while i<j do
       begin
         if v[i].c>v[j].c then
           begin
           aux:=v[i];
           v[i]:=v[j];
           v[j]:=aux;
           aux2:=di;
           di:=dj;
           dj:=aux2;
           end;
     i:=i+di;
     j:=j-dj;
     end;
     pivot:=i;
  end;
procedure sort(st,sf:longint);
var p:longint;
  begin
    if st<sf then
      begin
      p:=pivot(st,sf);
      sort(st,p-1);
      sort(p+1,sf);
      end;
  end;
begin
assign(f,'apm.in'); reset(f);
assign(g,'apm.out'); rewrite(g);
readln(f,n,m);
for i:=1 to m do
begin
read(f,v[i].x,v[i].y,v[i].c);
end;
{sortare;}
sort(1,m);
for i:=1 to n do
t[i]:=-1;
for i:=1 to m do
begin
a:=tata(v[i].x);
b:=tata(v[i].y);
if a<>b then
begin
t[a]:=t[a]+t[b];
t[b]:=a;
suma:=suma+v[i].c;
k:=k+1;
nr[k]:=i;
end;
end;
writeln(g,suma);
writeln(g,k);
for i:=1 to k do
writeln(g,v[nr[i]].x,' ',v[nr[i]].y);
close(f);
close(g);
end.