uses crt;
type rekord=record
      a,b,c:longint;
     end;
     vektor=array[1..400000] of rekord;
     vektor1=array[1..400000] of longint;
var f,g:text;
    v,v2:vektor;
    v1:vektor1;
    benne,benne1:boolean;
    i,a1,b1,c1,db,s,n,m,hely,min,me,db1:longint;
procedure Quick(bal,jobb:longint);
 var i,j,kozep,x:longint;
     temp:rekord;
 begin
  i:=bal;
  j:=jobb;
  kozep:=v[(i+j) div 2].c;
  while i<=j do
   begin
    while v[i].c<kozep do
     inc(i);
    while v[j].c>kozep do
     dec(j);
    if i<=j
     then
      begin
       temp:=v[i];
       v[i]:=v[j];
       v[j]:=temp;
       inc(i);
       dec(j);
      end;
 end;
 if bal<j
  then
   Quick(bal,j);
 if i<jobb
  then
  Quick(i,jobb);
 end;
begin
clrscr;
assign(f,'apm.in');
reset(f);
readln(f,n,m);
for i:= 1 to m do
 begin
  readln(f,a1,b1,c1);
  v[i].a:=a1;
  v[i].b:=b1;
  v[i].c:=c1;
 end;
close(f);
Quick(1,m);
{for i:= 1 to m do
 write(v[i].c,' '); }
for i:= 1 to n do
 v1[i]:=i;
hely:=1;
db:=0;
s:=0;
repeat
benne1:=false;
db1:=1;
while (not benne1) and (db1<=n) do
 begin
  inc(db1);
  if v1[db1]<>v1[1]
   then
    benne1:=true;
 end;
{for i:= 2 to n do
 if v1[i]<>v1[1]
  then
   benne1:=true; }
if benne1
 then
  begin
  if v1[v[hely].a]<>v1[v[hely].b]
   then
    begin
    me:=v1[v[hely].b];
    for i:= 1 to n do
     if v1[i]=me
      then
       v1[i]:=v1[v[hely].a];
    s:=s+v[hely].c;
    inc(db);
    v2[db].a:=v[hely].a;
    v2[db].b:=v[hely].b;
    end;
  end;
inc(hely);
until (not benne1) or (hely>m);
assign(g,'apm.out');
rewrite(g);
writeln(g,s);
writeln(g,db);
for i:= 1 to db do
 writeln(g,v2[i].a,' ',v2[i].b);
close(g);
end.