#include<stdio.h>
#include<algorithm>
#include<vector>


using namespace std;

const int maxn=400100;

int GR[maxn],X[maxn],Y[maxn],COST[maxn];
int N,M,REZ,INDICE[maxn];
vector<int> APM;

int Padure(int i)
{ 
	if(GR[i]==i) return i;
	GR[i]=Padure(GR[i]);
	return GR[i];
}
void reuniune(int i,int j)
{
	GR[Padure(i)]=Padure(j);
	
}
bool cmp(int i,int j)
     { return (COST[i]<COST[j]);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
		scanf("%d %d\n",&N,&M);
	for(int i=1;i<=M;i++)
{          
		scanf("%d %d %d",&X[i],&Y[i],&COST[i]);
		INDICE[i]=i;
}
     for(int i=1;i<=N;i++)GR[i]=i;
		 sort(INDICE+1,INDICE+M+1,cmp);
	
{    for(int i=1;i<=M;i++)
         {   if(Padure(X[INDICE[i]]) !=Padure(Y[INDICE[i]]))
                 REZ+=COST[INDICE[i]];
		 reuniune(X[INDICE[i]],Y[INDICE[i]]);
		 APM.push_back(INDICE[i]);
	     }
		 
}		
printf("%d\n",REZ);
printf("%d\n",N-1);
for(int i=0;i<N-1;++i)
	printf("%d %d\n",X[APM[i]],Y[APM[i]]);
	return 0;
}