#include<cstdio>
#include<algorithm>
using namespace std;
#define N 200001
#define M 400001
struct apm{int x,y;short int c;}v[M];
struct apm1{int x,y;}rez[M];
int gr[N],n,m,num,cost,nr,ind[N];
bool viz[N];
bool compar(int a,int b)
{
	return v[a].c<=v[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);
		ind[i]=i;
		if (i<=n)
			gr[i]=i;
	}
	sort(ind+1,ind+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;++i)
	{
		int g=grupa(v[ind[i]].x),g1=grupa(v[ind[i]].y);
		if (g!=g1)
		{
			cost+=v[ind[i]].c;
			unesc(v[ind[i]].x,v[ind[i]].y);
			rez[++num].x=v[ind[i]].x;
			rez[num].y=v[ind[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;
}