#include <stdio.h>
#include <algorithm>
#define NMAX 200005
#define LMAX 400005
using namespace std;
int n,m,rez,r;
struct muchie{int a,b,c;};
muchie A[LMAX],sol[NMAX];
int root[NMAX],grd[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i;
	for (i=1; i<=m; i++)
		scanf("%d%d%d",&A[i].a,&A[i].b,&A[i].c);
}
void init()
{
	int i;
	for (i=1; i<=n; i++)
		root[i]=i,grd[i]=1;
}
inline int find_root(int nod)
{
	int x=nod,y;
	while (root[x]!=x) x=root[x];
	while (root[nod]!=nod)
	{
		y=nod;
		nod=root[nod];
		root[y]=x;
	}
	return x;
}
void unite(int x,int y)
{
	if (grd[x]<grd[y])
		root[x]=y,grd[y]+=grd[x];
	else
		root[y]=x,grd[x]+=grd[y];
}
bool comp(muchie x,muchie y)
{
	return x.c<y.c;
}
void solve()
{
	init();
	sort(A+1,A+m+1,comp);
	int i;
	for (i=1; i<=m; i++)
		if (find_root(A[i].a)!=find_root(A[i].b))
		{
			rez+=A[i].c;
			sol[++r]=A[i];
			unite(find_root(A[i].a),find_root(A[i].b));
		}
		
	printf("%d\n%d\n",rez,n-1);
	for (i=1; i<n; i++)
		printf("%d %d\n",A[i].a,A[i].b);
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	read();
	solve();
	return 0;
}