#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 200010
#define M 400010
struct graf
{
	int x,y;
	short int c;
};
int n,m;
graf v[M];
int ind[M],t[N],gr[N];
int cost,rez[N];
inline void citire()
{
	scanf("%d%d",&n,&m);
	for(int i=0; i<m; ++i)
	{
		scanf("%d%d%hd",&v[i].x,&v[i].y,&v[i].c);
		ind[i]=i;
	}
}
int find(int x)
{
	int r=x;
	for(; t[r]!=r; r=t[r])
		;
	while(t[x]!=x)
	{
		int aux=t[x];
		t[x]=r;
		x=aux;
	}
	return r;
}
void reuniune(int x,int y)
{
	if(gr[x]<gr[y])
		t[x]=y;
	else
		t[y]=x;
	if(gr[x]==gr[y])
		++gr[x];
}
bool compar(const int &x,const int &y)
{
	return (v[x].c<v[y].c);
}
inline void rezolva()
{
	for(int i=1; i<=n; ++i)
	{
		t[i]=i;
		gr[i]=1;
	}
	sort(ind,ind+m,compar);
	int n1=n-1;
	for(int i=0; i<m && rez[0]!=n1; ++i)
	{
		int nod=ind[i];
		if(find(v[nod].x)!=find(v[nod].y))
		{
			cost+=v[nod].c;
			rez[++rez[0]]=nod;
			reuniune(find(v[nod].x),find(v[nod].y));
		}
	}
}
inline void scrie()
{
	printf("%d\n%d\n",cost,n-1);
	for(int i=1; i<=rez[0]; ++i)
		printf("%d %d\n",v[rez[i]].x,v[rez[i]].y);
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	rezolva();
	scrie();
	return 0;
}