#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int cMin,n,m;
struct p
{
	int x,y,c;
	p(const int X,const int Y,const int C)
	{
		x=X;y=Y;c=C;
	}
};
vector <p> a;
vector <int> tata(200001),rang(200001),rez;
inline bool cmp(p a,p b)
{
	return a.c<b.c;
}
int Find(int N)
{
	int root,aux;
	for(root=N;tata[root]!=root;root=tata[root]);
	while(tata[N]!=N)
	{
		aux=tata[N];
		tata[N]=root;
		N=aux;
	}
	return root;
}
void Merge(int N1,int N2)
{
	if(rang[N1]>rang[N2])
		tata[N2]=N1;
	else
		if(rang[N2]>rang[N1])
			tata[N1]=N2;
	if(rang[N1]==rang[N2])
	{
		tata[N1]=N2;
		rang[N2]++;
	}
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		a.push_back(p(x,y,c));
	}
	sort(a.begin(),a.end(),cmp);
	for(int i=1;i<=n;i++)
		tata[i]=i,rang[i]=1;
	for(int i=0;i<m;i++)
	{
		int rX=Find(a[i].x);
		int rY=Find(a[i].y);
		if(rX!=rY)
		{
			cMin+=a[i].c;
			Merge(rX,rY);
			rez.push_back(i);
		}
	}
	printf("%d\n%d\n",cMin,(int)rez.size());
	for(int i=0;i<(int)rez.size();i++)
		printf("%d %d\n",a[rez[i]].x,a[rez[i]].y);
	return 0;
}