{arbore partial de cost minim}
type muchie=record
            x,y:longint;
            cost:integer;
            end;
     extrem=record
            x,y:longint;
            end;

var l:array[1..200000] of longint;
    u:array[1..500000] of muchie;
    dr:array[1..500000] of extrem;
    n,m,cost,k:longint;

procedure citire;
var i:longint;
begin
assign(input,'apm.in'); reset(input);
readln(n,m);
for i:=1 to m do readln(u[i].x,u[i].y,u[i].cost);
close(input);
end;

procedure qsort(l,r:integer);
var i,j:longint;
    x:integer;
    aux:muchie;
begin
i:=l;
j:=r;
x:=u[(i+j) div 2].cost;

repeat
 while u[i].cost<x do inc(i);
 while x<u[j].cost do dec(j);

 if i<=j then
    begin
    aux:=u[i];
    u[i]:=u[j];
    u[j]:=aux;
    inc(i);
    dec(j);
    end;

until i>j;

if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;


procedure kruskal;
var i,j,v,w:longint;
begin

k:=0;
i:=1;
cost:=0;
for j:=1 to n do l[j]:=j;

while k<n-1 do
      begin
      if l[u[i].x]<>l[u[i].y] then
         begin
         inc(k);
         cost:=cost+u[i].cost;
         dr[k].x:=u[i].x;
         dr[k].y:=u[i].y;
         v:=l[u[i].x];
         w:=l[u[i].y];

         for j:=1 to n do
             if l[j]=v then l[j]:=w;
         end;
      inc(i);
      end;
end;


procedure afisare;
var i:longint;
begin
assign(output,'apm.out'); rewrite(output);
writeln(cost);
writeln(k);
for i:=1 to k do writeln(dr[i].x,' ',dr[i].y);
close(output);
end;

begin
citire;
qsort(1,m);
kruskal;
afisare;
end.