#include <cstdio>
#include <algorithm>
using namespace std;

struct muchie{ int e1,e2,cost;};

muchie G[400001];
int A[200001],c[200001];
int n,m;

bool comp(muchie a,muchie b){
	return a.cost<b.cost;
}

int main(){
	int s,i,j,NrMSel=0,min,max;
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i) scanf("%d%d%d",&G[i].e1,&G[i].e2,&G[i].cost),c[i]=i;
	
	sort(G+1,G+m+1,comp);
	
	for(i=1; NrMSel<n-1; ++i)
		if (c[G[i].e1]!=c[G[i].e2]){
			A[++NrMSel]=i;
			if (c[G[i].e1]<c[G[i].e2]){
				min=c[G[i].e1];
				max=c[G[i].e2];
				}
			else{
				min=c[G[i].e2];
				max=c[G[i].e1];
				}
			for(j=1;j<=n;++j)
				if (c[j]==max) c[j]=min;
			}
	
	for(i=1;i<=NrMSel;++i) s+=G[A[i]].cost;
	printf("%d\n%d\n",s,NrMSel);
	for(i=1;i<=NrMSel;++i) printf("%d %d\n",G[A[i]].e1,G[A[i]].e2);
	return 0;
}