uses crt;
type rekord=record
      a,b,c:integer;
      d:boolean;
     end;
     vektor=array[1..50000] of rekord;
     vektor1=array[1..10000] 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:integer);
 var i,j,kozep,x:integer;
 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
       x:=v[i].c;
       v[i].c:=v[j].c;
       v[j].c:=x;
       x:=v[i].b;
       v[i].b:=v[j].b;
       v[j].b:=x;
       x:=v[i].a;
       v[i].a:=v[j].a;
       v[j].a:=x;
       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,'apm1.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,'apm1.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.