program apm_prim;
const inf=3000;
var f,g:text;
    a:array[1..200000,1..200000] of integer;
    sel:array[1..200000] of boolean;
    d,t:array[1..200000] of integer;
    n,m,cost:longint;

procedure citire;
var i,j,x,y,c:longint;
begin
readln(f,n,m);
fillchar(sel,n,false);
fillchar(t,n,0);
for i:=1 to n do
  for j:=1 to n do
    a[i,j]:=inf;
for i:=1 to n do a[i,i]:=0;
for i:=1 to m do begin
  readln(f,x,y,c);
  a[x,y]:=c;
  a[y,x]:=c;
  end;
end;

procedure pr;
var i,min,nod,j:longint;
begin
d[1]:=0;
sel[1]:=true;
t[1]:=0;
cost:=0;
for i:=2 to n do begin
  d[i]:=a[i,1];
  t[i]:=1;
  end;
for i:=1 to n-1 do begin
  min:=inf;
  for j:=1 to n do
    if not sel[j] and (d[j]<min) then begin
      min:=d[j];
      nod:=j;
      end;
  sel[nod]:=true;
  inc(cost,d[nod]);
  for j:=1 to n do
    if (a[nod,j]<d[j]) and not sel[j] then begin
      d[j]:=a[nod,j];
      t[j]:=nod;
      end;
  end;
end;

procedure scriere;
var i:longint;
begin
writeln(g,cost);
writeln(g,n-1);
for i:=1 to n do
  if t[i]<>0 then writeln(g,i,' ',t[i]);
end;

begin
assign(f,'apm.in');
assign(g,'apm.out');
reset(f);
rewrite(g);
citire;
pr;
scriere;
close(g);
end.