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

#define NMAX 200001
#define MMAX 400001

struct muchie {
	int x,y,cost;
	bool operator < (const muchie &c) const {
		return cost<c.cost;
	}
};

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

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

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

int main ()
{
	int i,n,m,cmin,k;
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>v[i].x>>v[i].y>>v[i].cost;
	f.close();
	sort(v+1,v+m+1);
	for(i=1;i<=n;i++) {
		p[i]=i;
		rang[i]=1;
	}
	cmin=0;
	k=0;
	for(i=1;i<=m && k<=n-1;i++) {
		if(multime(v[i].x)==multime(v[i].y))
			continue;
		cmin=cmin+v[i].cost;
		sol.push_back(v[i]);
		uneste(v[i].x,v[i].y);
		k++;
	}
	g<<cmin<<'\n'<<n-1<<'\n';
	for(vector <muchie> :: iterator it=sol.begin();it!=sol.end();it++)
		g<<it->x<<" "<<it->y<<'\n';
	g.close();
	return 0;
}