#include <fstream>

using namespace std;

#define N 200000

int n, m, msel=0, bheap[N*2], bheap_n=0, CN[N+1], MS[N];
long long sum=0;
struct muchie{
	int c1, c2, cost;
};
muchie M[N*2];
struct nod{
	int inf;
	nod *n;
};
struct lista{
	nod *p, *u;
	lista(){
		p=u=NULL;
	}
	void push_back(int a){
		nod *z=new nod;
		z->inf=a;
		z->n=NULL;
		if(!p)
			p=z;
		if(u)
			u->n=z;
		u=z;
	}

};
lista NN[N+1];

inline int bheap_parinte(int i){
	return (i-1)/2;
}
inline int bheap_stanga(int i){
	return i*2+1;
}
inline int bheap_dreapta(int i){
	return i*2+2;
}
int varf(){
	--bheap_n;
	swap(bheap[0], bheap[bheap_n]);
	int i=0, s, d, ni;
	s=bheap_stanga(i);
	d=s+1;
	while(1){
		if(d>=bheap_n){
			if(s>=bheap_n)
				break;
			if(M[bheap[i]].cost > M[bheap[s]].cost)
				swap(bheap[i], bheap[s]);
			break;
		}
		if(M[bheap[s]].cost < M[bheap[d]].cost)
			ni=s;
		else
			ni=d;
		if(M[bheap[i]].cost > M[bheap[ni]].cost)
			swap(bheap[i], bheap[ni]);
		else
			ni=0;
		if(!ni)
			break;
		i=ni;
		s=bheap_stanga(i);
		d=s+1;
	}
	return bheap[bheap_n];
}
void adauga(int x){
	int i=bheap_n++, p;
	bheap[i]=x;
	while(1){
		p=bheap_parinte(i);
		if(p==i || p<0)
			return;
		if(M[bheap[i]].cost >= M[bheap[p]].cost)
			return;
		swap(bheap[i], bheap[p]);
		i=p;
	}
}

int main(){
	int i;
	{//citire
		ifstream fp("apm.in");
		fp>>n>>m;
		for(i=0; i<m; i++){
			fp>>M[i].c1>>M[i].c2>>M[i].cost;
			NN[M[i].c1].push_back(i);
			NN[M[i].c2].push_back(i);
		}
		fp.close();
	}
	{//Prim
		for(i=1; i<=n; i++)
			CN[i]=i;
		nod *q;
		int a, b;
		for(q=NN[1].p; q; q=q->n)//adauga toti vecinii lui 1
			adauga(q->inf);
		while(msel<n-1){
			a=varf();
			if(CN[M[a].c1] == CN[M[a].c2])
				continue;
			if(CN[M[a].c1] == 1)
				b=M[a].c2;
			else
				b=M[a].c1;
			MS[msel++]=a;
			sum+=M[a].cost;
			CN[b]=1;
			for(q=NN[b].p; q; q=q->n){//adauga toti vecinii nodului nou adaugat care nu sunt selectati
				if(M[q->inf].c1 == b)
					a=M[q->inf].c2;
				else
					a=M[q->inf].c1;
				if(CN[a] != 1)
					adauga(q->inf);
			}
		}
	}
	{//afisare
		ofstream fp("apm.out");
		fp<<sum<<"\n"<<msel<<"\n";
		for(i=0; i<msel; i++)
			fp<<M[MS[i]].c1<<" "<<M[MS[i]].c2<<"\n";
		fp.close();
	}
	return 0;
}