#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");

const int NMAX=2e5+5,MMAX=4e5+5;
int n,m,x,y,cost,P[NMAX],rez;
vector <pair <int,int> > ans;
vector <pair <int, pair <int,int> > > v;
int radacina(int x)
{
	if(P[x]<0) return x;
	P[x]=radacina(P[x]);
	return P[x];
}
void reuniune(int x,int y)
{
	if(-P[x]>-P[y])
	{
		P[x]+=P[y];
		P[y]=x;
	}
	else
	{
		P[y]+=P[x];
		P[x]=y;
	}
}
int main()
{
	fi>>n>>m;
	for(int i=1;i<=m;i++)
	{
		fi>>x>>y>>cost;
		v.push_back({cost,{x,y}});
	}
	sort(v.begin(),v.end());
	for(int i=1;i<=n;i++)
		P[i]=-1;
	for(int i=0;i<m;i++)
	{
		x=v[i].second.first;
		y=v[i].second.second;
		cost=v[i].first;
		if(radacina(x)!=radacina(y))
		{
			reuniune(radacina(x),radacina(y));
			rez+=cost;
			ans.push_back({x,y});
		}
	}
	fo<<rez<<"\n"<<n-1<<"\n";
	for(int i=0;i<ans.size();i++)
		fo<<ans[i].first<<" "<<ans[i].second<<"\n";

	fi.close();
	fo.close();
	return 0;
}