#include<cstdio>
#include<algorithm>
using namespace std;
#define N 200001
#define M 500001
struct apm{int x,y,c;}v[M];
struct apm1{int x,y;}rez[N];
int gr[N],n,m,num,cost,nr;
bool viz[N];
bool compar(const apm&a,const apm&b)
{
	return a.c<=b.c;
}
void citire()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
		if (i<=n)
			gr[i]=i;
	}
	sort(v+1,v+1+m,compar);
}
int grupa(int i)
{
	if (gr[i]==i)
	return i;
	gr[i]=grupa(gr[i]);
	return gr[i];
}
void unesc(int i,int j)
{
	gr[grupa(i)]=grupa(j);
}
void apm()
{
	int i;
	for (i=1; i<=m&&nr<n;++i)
	{
		int g=grupa(v[i].x),g1=grupa(v[i].y);
		if (g!=g1)
		{
			cost+=v[i].c;
			unesc(v[i].x,v[i].y);
			if (!viz[v[i].x])
			{
			++nr;
			viz[v[i].x]=true;
			}
			if (!viz[v[i].y])
			{
			++nr;
			viz[v[i].y]=true;
			}
			rez[++num].x=v[i].x;
			rez[num].y=v[i].y;
		}
	}

}
void afis()
{
	printf("%d\n%d\n",cost,num);
	for (int i=1; i<=num; ++i)
	printf("%d %d\n",rez[i].x,rez[i].y);
}
int main()
{
	citire();
	apm();
	afis();
	return 0;
}