#include<fstream>
#include<vector>
#include<algorithm>
#define nmax 200005
#define mmax 400005
#define fill(v,n) for(i=1;i<=n;i++) v[i]=i;
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct NOD
{
	int x,y,c;
}nods[nmax];
int G[nmax],n,m,ans,ind[nmax];
vector<int> v;
bool cmp(int i,int j)
{
	return (nods[i].c<nods[j].c);
}
inline int grupa(int i)
{
	if(G[i]==i)
		return i;
	G[i]=grupa(G[i]);
	return G[i];
}
void un(int i,int j)
{
	G[grupa(i)]=grupa(j);
}
int main()
{
	f>>n>>m;
	int i;
	for(i=1;i<=m;i++)
		f>>nods[i].x>>nods[i].y>>nods[i].c;
	fill(ind,m);
	fill(G,n);
	sort(ind+1,ind+m+1,cmp);
	for(i=1;i<=m;i++)
		if(grupa(nods[ind[i]].x)!=grupa(nods[ind[i]].y))
		{
			ans+=nods[ind[i]].c;
			un(nods[ind[i]].x,nods[ind[i]].y);
			v.push_back(ind[i]);
		}
	g<<ans<<'\n';
	g<<n-1<<'\n';
	for(i=0;i<n-1;i++)
		g<<nods[v[i]].x<<' '<<nods[v[i]].y<<'\n';
	f.close();
	g.close();
	return 0;
}