# include <cstdio>
# include <algorithm>
# include <vector>
# include <cstring>
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]);
}
char buff[4096]; short pos=4096;
inline char nextChar()
{
	if(pos==4096)
	{
		fread(buff,1,4096,stdin);
		pos=0;
	}
	return buff[pos++];
}
inline int nextInt()
{
	int nr=0;
	char ch=nextChar(),sign=1;
	while((ch<'0' || ch>'9') && ch!='-')
		ch=nextChar();
	if(ch=='-')
	{
		sign=-1;
		ch=nextChar();
	}
	while(ch>='0' && ch<='9')
	{
		nr=nr*10+ch-'0';
		ch=nextChar();
	}
	return sign*nr;
}
int main()
{
	long long ct=0;
	int n,m,k;
	n=nextInt();
	m=nextInt();
	int i,j;
	for(i=1;i<=m;++i)
	{
		X[i]=nextInt();
		Y[i]=nextInt();
		C[i]=nextInt();
	}//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));
}