#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 400100;
int GR[maxn] , X[maxn] , Y[maxn] ,IND[maxn] , C[maxn];
int n , m ,  ans , *sol ;

struct cmp { bool operator() (int i,int j) 
		{return C[i] < C[j];}
};

int grupa(int i)
{
	if(GR[i]==i) return i;
	return  GR[i] = grupa(GR[i]);
}

void reuniune(int i,int j)
{
	GR[grupa(i)] = grupa(j);
}

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],&C[i]) , IND[i] = i;

	for(int i=1;i<=n;++i) GR[i] = i;

	sort(IND + 1,IND + m + 1,cmp());
	sol = new int[n+1000] , sol[0] = 0;
	for(int i=1;i<=m;++i)
		if(grupa(X[IND[i]])!=grupa(Y[IND[i]]))
			ans +=C[IND[i]] , reuniune(X[IND[i]],Y[IND[i]]) , sol[++sol[0]] = IND[i]; 
	
	printf("%d\n%d\n",ans,n-1);
	for(int i=1;i<n;++i)
		printf("%d %d\n",X[sol[i]],Y[sol[i]]);
	return 0;
}