#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
#define nmax 200005
struct muchie{ int x; int y; int c; };
vector<muchie> apm,v;
int t[nmax];
int n,m;
void citire ()
{
	ifstream fin("apm.in");
	int i;
	muchie aux;
	fin>>n>>m;
	for(i=1;i<=n;i++) t[i]=i;
	for(i=1;i<=m;i++)
	{
		fin>>aux.x>>aux.y>>aux.c;
		v.push_back(aux);
	}
	fin.close();
}
int cmp(struct muchie x, struct muchie y) 
{ 
    
return x.c < y.c; 
} 
 
 
int tata(int x)
{
	if (x != t[x]) t[x] = tata(t[x]);
	return t[x];
}

int main ()
{
	int i,x,y,cost=0;
	citire ();
	sort(v.begin(),v.end(),cmp);
	for(i=0;i<m;i++)
	{
		x=tata(v[i].x); y=tata(v[i].y);
		if(x!=y)
		{
			cost+=v[i].c;
			t[x]=y;
			apm.push_back(v[i]);
		}
	}
	ofstream fout("apm.out");
	fout<<cost<<"\n";
	fout<<apm.size()<<"\n";
	for(i=0;i<apm.size();i++)
		fout<<apm[i].x<<' '<<apm[i].y<<"\n";
	fout.close();
	return 0;
}