#include <fstream>
#include <vector>
#include <list>

using namespace std;

#define N 200000

int n, m, msel=0, bheap[N], bheap_n=0, CN[N+1];
long long sum=0;
struct muchie{
	int c1, c2, cost;
};
muchie M[N*2], MS[N];
vector<list<int>> NN;


int bheap_parinte(int i){
	return (i-1)/2;
}
int bheap_stanga(int i){
	return i*2+1;
}
int bheap_dreapta(int i){
	return i*2+2;
}
int varf(){
	int ret=bheap[0];
	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;
		}
		ni=0;
		if(M[bheap[i]].cost > M[bheap[d]].cost){
			swap(bheap[i], bheap[d]);
			ni=d;
		}
		if(M[bheap[i]].cost > M[bheap[s]].cost){
			swap(bheap[i], bheap[s]);
			ni=s;
		}
		if(!ni)
			break;
		i=ni;
		s=bheap_stanga(i);
		d=s+1;
	}
	return ret;
}
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;
		NN.resize(n+1);
		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;
		list<int>::iterator it;
		int a, b;
		for(it=NN[1].begin(); it != NN[1].end(); it++)//adauga toti vecinii lui 1
			adauga(*it);
		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++]=M[a];
			sum+=M[a].cost;
			CN[b]=1;
			for(it=NN[b].begin(); it != NN[b].end(); it++){//adauga toti vecinii nodului nou adaugat care nu sunt selectate
				if(M[*it].c1 == b)
					a=M[*it].c2;
				else
					a=M[*it].c1;
				if(CN[a] != 1)
					adauga(*it);
			}
		}
	}
	{//afisare
		ofstream fp("apm.out");
		fp<<sum<<"\n"<<msel<<"\n";
		for(i=0; i<msel; i++)
			fp<<MS[i].c1<<" "<<MS[i].c2<<"\n";
		fp.close();
	}
	return 0;
}