program arborepartialdecostminim;
const nmax = 200001;
      Mmax = 400001;
type element = record
        x,y:longint;
        c:integer;
        end;
var f,g:text;
    v:array[1..Mmax] of element;
    tata,muchii:array[1..Nmax] of longint;
    n,m,i,k,a,b,suma:longint;
    bufin,bufout:array[1.. 1 shl 17] of char;
function pivot(st, dr:longint):longint;
var aux, i, j, di, dj:longint;
    aux2 : element;
begin
        i := st; j := dr;
        di := 0; dj := 1;
        while i < j do
                begin
                  if v[i].c > v[j].c then
                        begin
                          aux2 := v[i];
                          v[i] := v[j];
                          v[j] := aux2;
                          aux := di;
                          di := dj;
                          dj := aux;
                        end;
                i := i + di;
                j := j - dj;
                end;
        pivot := i;
end;
procedure sort(st, dr:longint);
var p:longint;
begin
        if st < dr then
                begin
                  p := pivot(st, dr);
                  sort(st, p-1);
                  sort(p+1, dr);
                end;
end;
function radacina(nod:longint):longint;
begin
        if tata[nod] = 0 then
                radacina := nod
           else
                begin
                  tata[nod] := radacina(tata[nod]);
                  radacina :=  tata[nod];
                end;
end;
begin
        assign(f,'apm.in'); reset(f);
        assign(g,'apm.out'); rewrite(g);
        settextbuf(f,bufin); settextbuf(f,bufout);
        readln(f,n,m);
        for i := 1 to m do
                readln(f,v[i].x, v[i].y, v[i].c);
        sort(1,m);
        a := 0; b := 0; suma := 0; k := 0;
        for i := 1 to m do
                begin
                a := radacina(v[i].x); b := radacina(v[i].y);
                if a <> b then
                        begin
                          tata[b] := a;
                          inc(k);
                          muchii[k] := i;
                          suma := suma + v[i].c;
                        end;
                end;
        writeln(g,suma);
        writeln(g,k);
        for i := 1 to k do
                writeln(g, v[muchii[i]].x,' ',v[muchii[i]].y);
        close(f); close(g);
end.