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:integer;
begin
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);
for i:= 1 to m do
 v[i].d:=false;
for i:= 1 to n do
 v1[i]:=i;
repeat
min:=maxint;
benne:=false;
for i:= 1 to m do
 if (v[i].c<min) and (not v[i].d)
  then
   begin
   min:=v[i].c;
   benne:=true;
   hely:=i;
   end;
benne1:=false;
for i:= 2 to n do
 if v1[i]<>v1[1]
  then
   benne1:=true;
if benne and benne1
 then
  begin
  v[hely].d:=true;
  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].b;
    v2[db].b:=v[hely].a;
    end;
  end;
until (not benne1) or (not benne);
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.