#include<fstream>
#include<vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int Nmax = 200005;
const int Mmax = 400005;
int N,M;
int insideAPM[Nmax];
struct vertex{
	int dest,cost;
};
vector<vertex> G[Nmax];
struct apm_link{
	int a,b;
};
vector<apm_link> APM;
int ans;
struct heap_item{
	int val,node,origin;
} H[Nmax+Mmax]; int L;
void swap(int a,int b){
	heap_item X=H[a];
	H[a]=H[b];
	H[b]=X;
}
void upheap(int i){
	if(i/2>0 && H[i/2].val>H[i].val){
		swap(i/2,i);
		upheap(i/2);
	}
}
void downheap(int i){
	if(2*i+1<=L && H[2*i+1].val<H[i].val && H[2*i+1].val<=H[2*i].val){
		swap(i,2*i+1);
		downheap(2*i+1);
	}
	else if(2*i<=L && H[2*i].val<H[i].val){
		swap(2*i,i);
		downheap(2*i);
	}
}
heap_item First(){
	heap_item X=H[1];
	swap(1,L);
	--L;
	downheap(1);
	return X;
}
void Push(heap_item X){
	H[++L]=X;
	upheap(L);
}
int main(){
	in>>N>>M;
	for(int i=1;i<=M;i++){
		int x,y,c;
		vertex u;
		in>>x>>y>>c;
		u.cost=c;
		u.dest=y;
		G[x].push_back(u);
		u.dest=x;
		G[y].push_back(u);
	}
	for(vector<vertex>::iterator it=G[1].begin();it!=G[1].end();++it){
		heap_item start;
		start.val=it->cost;
		start.node=it->dest;
		start.origin=1;
		Push(start);
	}
	insideAPM[1]=1;
	while(L>0){
		heap_item p=First();
		if(!insideAPM[p.node]){
			insideAPM[p.node]=1;
			ans+=p.val;
			apm_link u;
			u.a=p.origin;
			u.b=p.node;
			APM.push_back(u);
			for(vector<vertex>::iterator it=G[p.node].begin();it!=G[p.node].end();++it){
				if(!insideAPM[it->dest]){
					heap_item pp;
					pp.val=it->cost;
					pp.node=it->dest;
					pp.origin=p.node;
					Push(pp);
				}
			}
		}
	}
	out<<ans<<'\n';
	out<<APM.size()<<'\n';
	for(vector<apm_link>::iterator it=APM.begin();it!=APM.end();++it){
		out<<it->a<<' '<<it->b<<'\n';
	}
	return 0;
}