#include<fstream.h>
ifstream f("apm.in");
ofstream g("apm.out");
#define Nmax 200100
#define Mmax 400100
long n,m,N,t[Nmax],nr,S;
struct elem
{
	int long x,y;
	int cost;
}h[Mmax];
void urca(long k)
{
	if(k>1)
	{
		if(h[k/2].cost<h[k].cost)
		{
			elem c=h[k];
			h[k]=h[k/2];
			h[k/2]=c;
			urca(k/2);
		}
	}
}
void coboara(long k,long m)
{
	long fiu=k;
	if(2*k<=m)
	{
		if(2*k+1<m&&h[fiu].cost<h[2*k+1].cost)
			fiu=2*k+1;
		if(h[2*k].cost>h[fiu].cost)
			fiu=2*k;
		if(fiu!=k)
		{
			elem c=h[fiu];
			h[fiu]=h[k];
			h[k]=c;
			coboara(fiu,m);
		}
	}
}

void citire()
{
	f>>n>>m;  N=m;
	for(long i=1;i<=m;i++)
	{
		f>>h[i].x>>h[i].y>>h[i].cost;
		urca(i);
	}
}
void sort()
{
	while(N>0)
	{
		elem c=h[1];
		h[1]=h[N];
		h[N]=c;
		N--;
		coboara(1,N);
	}
}
void init()
{
	for(long i=1;i<=n;i++)
		t[i]=i;
}
long verif(long x)
{
	if(t[x]==x)
	{
		return x;
	}
	else
		verif(t[x]);
}
void program()
{
	S+=h[1].cost;nr=1;
	t[h[1].y]=h[1].x;
	long i=2;
	while(i<=m)
	{
		long rx=verif(h[i].x),ry=verif(h[i].y);
		if(rx!=ry)
		{
			if(rx<ry)
			t[h[i].y]=rx;
			else
			t[h[i].x]=ry;
			nr++; S+=h[i].cost;
		}
		else
		{
			h[i].x=0;
			h[i].y=0;
			h[i].cost=0;
		}
		i++;
	}

}
int main()
{
	citire();
	init();
	sort();
	program();
	g<<S<<'\n';
	g<<nr<<'\n';
	for(long i=1;i<=m&&nr;i++)
		if(h[i].x!=0&&h[i].y!=0&&h[i].cost!=0)
		{
			g<<h[i].x<<" "<<h[i].y<<'\n';
			nr--;
		}
 f.close();
 g.close();
 return 0;
}