const
	nmax=20001;
	mmax=40001;
	INF=maxint div 2;
var
	c:array[1..nmax,1..nmax] of longint;
	d,t:array[1..nmax] of longint;
	use:array[1..nmax] of boolean;
	n,m:longint;
	i,ii,jj,cc:longint;
	
procedure prim(x:longint);
	var
		min,cost,nod,ns:longint;
		sola,solb:array[1..mmax] of integer;
	begin
		fillchar(use,sizeof(use),false); //initializez datele
		fillchar(t,sizeof(t),0);
		cost:=0;
		ns:=0;
		for i:=1 to n do begin
			d[i]:=c[x,i]; //construiesc vectorul de costul pentru nodul radacina
			t[i]:=x;
		end;
		use[x]:=true; //marchez nodul ca folosit
		while true do begin
			min:=INF;
			nod:=-1;
			for i:=1 to n do begin
				if (use[i]=false) and (min>d[i]) then begin //aleg minimul dintre costurile nodurilor adiacente nodului "nod"
					min:=d[i];
					nod:=i;
				end;
			end;
			if (min=INF) then break; //daca am utilizat toate nodurile ies din ciclu
			
			use[nod]:=true; //marchez ca folosit
			inc(ns);
			sola[ns]:=t[nod]; //creez noul graf
			solb[ns]:=nod;
			inc(cost,d[nod]); //adaug la costul total
			
			for i:=1 to n do begin //adaug la vectorul de costuri costurile minime noului nod in cazul in care costul este mai mic decat costul nodului anterior
				if d[i]>c[nod,i] then begin
					d[i]:=c[nod,i];
					t[i]:=nod;
				end;
			end;
		end;
		writeln(cost);
		writeln(ns);
		for i:=1 to ns do
			writeln(sola[i],' ',solb[i]);
	end;
	
begin
	assign(input,'apm.in');reset(input);
	assign(output,'apm.out');rewrite(output);
    fillchar(c,sizeof(c),0);
	readln(n,m);
	for i:=1 to m do begin //citest muchia si costul intr-o matrice
		readln(ii,jj,cc);
		c[ii,jj]:=cc;
		c[jj,ii]:=cc;
	end;
	prim(1); //apelez procedure pentru un nod oarecare //algoritmul lui prim
end.