#include<stdio.h>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
#include<functional>

#define Mmax 400001
#define Nmax 200001
#define d first
#define n1 second.first
#define n2 second.second
#define tip pair<int,pair<int,int> >


using namespace std;

FILE *in,*out;
int n,m,cost;
int nod1,nod2,dist;
int tata[Nmax];

priority_queue<tip, vector<tip >, greater<tip> >q;
vector<pair<int,int> > answer;

int getRoot(int nod);

int main(void)
{
	in=fopen("kruskal.in","rt");
	fscanf(in,"%d%d",&n,&m);
	for(int i=0;i<m;++i)
	{	
		fscanf(in,"%d%d%d",&nod1,&nod2,&dist);
		q.push(make_pair(dist,make_pair(nod1,nod2)));
	}	

	while(!q.empty())
	{
		pair<int,pair<int,int> > curent=q.top();
		q.pop();
		int w=getRoot(curent.n1);
		int q=getRoot(curent.n2);
		if(w!=q)
		{			
			tata[q]=w;
			cost+=curent.d;
			answer.push_back(make_pair(curent.n1,curent.n2));
		}
			
	}	
	
	out=fopen("kruskal.out","wt");
	//for(int i=0;i<m;i++)
		//fprintf(out,"%d ",muchii[i].d);
	fprintf(out,"%d\n",cost);
	fprintf(out,"%d\n",answer.size());
	vector<pair<int,int> >:: iterator it,end=answer.end();
	for(it=answer.begin() ; it!=end ; ++it)
		fprintf(out,"%d %d\n",it->first,it->second);
	fclose(in);
	fclose(out);
	return 0;

}	

int getRoot(int nod)
{
	if(tata[nod])
	{
		tata[nod]=getRoot(tata[nod]);
		return tata[nod];
	}
	return nod;
	
}