type vect=array[-1..30] of integer;
var a:array[-1..30,-1..30] of integer;
    n:integer;
    S,T,C:vect;
    fis,out:text;

procedure Citeste;
var   i,j,k,m,x,y,c:integer;
begin
  assign (fis, 'apm.in'); reset (fis);
  readln (fis,n,m);
  for i:=1 to n do
     for j:=1 to n do
          a[i,j]:=0;
  for k:=1 to m do
  begin
        readln (fis,x,y,c);
        a[x,y]:=c;
        a[y,x]:=c;
  end;
  close(fis);
end;

procedure afisareArbore;
var i,suma,nrMuchii:integer;
begin
    assign (out, 'apm.out'); rewrite(out);
    suma:=0;
    for i:=1 to n do
      suma:=suma+C[i];
    writeln (out,suma);
    nrMuchii:=0;
    for i:=1 to n do
      if T[i]<>0 then nrMuchii:=nrMuchii+1;
    writeln (out,nrMuchii);
    for i:=2 to n do
     writeln (out,i,' ',T[i]);
    close(out);

end;

procedure formareArbore;
var k,i,j,start,cost_min,n1,n2:integer;
begin
    for i:=1 to n do
    begin
        S[i]:=0;
        T[i]:=0;
        C[i]:=0;
    end;
    start:=1;
    S[start]:=1;
    for k:=1 to n-1 do
    begin
        cost_min:=MAXINT;
        n1:=-1;
        n2:=-1;
        for i:=1 to n do
           for j:=1 to n do
               if (S[i]=1) and (S[j]=0) then
                   if (a[i,j]<>0) then
                       if (a[i,j]<cost_min) then
                       begin
                            cost_min:=a[i,j];
                            n1:=i;
                            n2:=j;
                       end;

        S[n2]:=1;
        T[n2]:=n1;
        C[n2]:=a[n1,n2];
    end;
end;

begin
    Citeste;
    formareArbore;
    afisareArbore ;
end.