#include<cstdio>
#include<algorithm>
using namespace std;
#define NM 400001
#define MM 200001
int x[NM],y[NM],z[NM],ind[NM],rez[MM],gr[MM],rang[MM];
int N,M,cost;
bool cmp(const int &i,const int &j)
{
	return z[i]<z[j];
}
int find(int x)
{
	if (x!=gr[x])
		gr[x]=find(gr[x]);
	return gr[x];
}
void unesc(int x, int y)
{
	if (rang[x]>rang[y])
		gr[x]=y;
	else
	{
		gr[y]=x;
		rang[x]+=(rang[x]==rang[y]);
	}
}
int main()
{
	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",&x[i],&y[i],&z[i]);
		ind[i]=i;
	}
	sort(ind+1,ind+1+M,cmp);
	for(int i=1; i<=N; ++i)
		gr[i]=i,rang[i]=0;
	for (int i=1; i<=M; ++i)
	{
		int u=find(x[ind[i]]);
		int v=find(y[ind[i]]);
		if (u==v)
			continue;
		unesc(v,u);
		cost+=z[ind[i]];
		rez[++rez[0]]=ind[i];
	}
	printf("%d\n%d\n",cost,rez[0]);
	for (int i=1; i<=rez[0]; ++i)
		printf("%d %d\n",x[rez[i]],y[rez[i]]);
	return 0;
}