#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

#define NMAX 200001
#define xx first
#define yy second

vector < pair < int , pair < int , int > > > v;
vector < pair < int , int > > sol;
int rang[NMAX],p[NMAX];

int multime(int x)
{
	int aux,r;
	r=x;
	while(r!=p[r]) 
		r=p[r];
	while(x!=r) {
		aux=p[x];
		p[x]=r;
		x=aux;
	}
	return r;
}

void uneste(int x, int y)
{
	x=multime(x);
	y=multime(y);
	if(rang[x]<=rang[y])
		p[x]=y;
	else p[y]=x;
	if(rang[x]==rang[y])
		rang[y]++;
}

int main ()
{
	int sum,i,n,m,y,x,cost;
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		v.push_back(make_pair(cost,make_pair(x,y)));
	}
	f.close();
	sum=0;
	for(i=1;i<=n;i++) {
		p[i]=i;
		rang[i]=1;
	}
	sort(v.begin(),v.end());
	for(i=0;i<=m-1;i++)
		if(multime(v[i].yy.xx)!=multime(v[i].yy.yy)) {
			sum=sum+v[i].xx;
			sol.push_back(make_pair(v[i].yy.xx,v[i].yy.yy));
			uneste(v[i].yy.xx,v[i].yy.yy);
		}
	g<<sum<<'\n'<<sol.size()<<'\n';
	for(i=0;i<=n-2;i++)
		g<<sol[i].xx<<" "<<sol[i].yy<<'\n';
	g.close();
	return 0;
}