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

#define NMAX 200010

int pr[NMAX],grd[NMAX],n,m;

struct edg{
	int x,y,c;
};

bool cmp(const edg a,const edg b){
	return a.c < b.c;
}
typedef vector<edg>::iterator iter;
vector<edg> g,res;

int find(int x){
	int p=x,y;
	while(pr[p]!=p)
		p=pr[p];
	
	while(pr[x]!=x)
		y=pr[x],pr[x]=p,x=y;
		
	return p;
}

void unite(int x,int y){
	x=find(x),y=find(y);
	
	if(grd[x]>grd[y]) pr[y]=x;	
	else pr[x]=y;
	
	if(grd[x]==grd[y]) grd[y]++;
}

int main(){
	FILE* fin=fopen("apm.in","r");
	FILE* fout=fopen("apm.out","w");
	
	fscanf(fin,"%d %d\n",&n,&m);
	
	g.resize(m);
	
	for(int i=0;i<=n;i++){
		pr[i]=i;
		grd[i]=1;
	}
	
	for(int i=0;i<m;i++){
		fscanf(fin,"%d %d %d\n",&g[i].x,&g[i].y,&g[i].c);
	}
	
	sort(g.begin(),g.end(),cmp);
	
	int cost=0;
	for(iter it=g.begin();it!=g.end();++it){
		if(find(it->x)!=find(it->y)){
			cost+=it->c;
			res.push_back(*it);	
			unite(it->x,it->y);
		}
	}	
	
	fprintf(fout,"%d\n%d\n",cost,res.size());
	
	for(iter it=res.begin();it!=res.end();++it){
		fprintf(fout,"%d %d\n",it->x,it->y);	
	}
	
	fclose(fin);
	fclose(fout);
	return 0;
}