# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
FILE *f=freopen("apm.in","r",stdin),*g=freopen("apm.out","w",stdout);
# define nmax 400001
int IND[nmax],X[nmax],Y[nmax],C[nmax],L[200001];
vector<int> A;
bool comp(int i,int j)
{
	return (C[i]<C[j]);
}
int main()
{
	long long ct=0;
	int n,m,k;
	scanf("%d%d",&n,&m);
	int i,j;
	for(i=1;i<=m;++i)
		scanf("%d%d%d",X+i,Y+i,C+i);//citim muchii si costurile atasate
	for(i=1;i<=m;++i) 
		IND[i]=i;//initializam indicii
	sort(IND+1,IND+m+1,comp);//ii sortam in functie de costuri pentru ai folosi pe post de costuri
	for(i=1;i<=n;++i) L[i]=i;
	int nr1,nr2;
	i=1,k=1;
	while(k<n)
	{
		if(L[X[IND[i]]]!=L[Y[IND[i]]])
		{
			++k;//adaugam o muchie
			A.push_back(X[IND[i]]);//salvam x
			A.push_back(Y[IND[i]]);//adugam y
			ct+=C[IND[i]];//actualizam costul
			nr1=L[X[IND[i]]];nr2=L[Y[IND[i]]];
			for(j=1;j<=n;++j)
				if(L[j]==nr2)
					L[j]=nr1;
		}
		++i;
	}
	printf("%lld\n%u\n",ct,A.size()/2);
	vector<int>::iterator its=A.begin(),ite=A.end();
	for(;its!=ite;its+=2)
		printf("%d %d\n",*its,*(its+1));
}