#include <fstream>
#include <algorithm>
#include <vector>
#define arm 400009
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,res,a[arm],b[arm],cost[arm],point[arm],MD[arm];
vector<int> R;

bool f(int i, int j)
{
	return (cost[i]<cost[j]);
}

int boss(int i)
{
	if(MD[i]==i) return i;
	MD[i]=boss(MD[i]);
	return MD[i];
}

void uneste(int i,int j)
{
	MD[boss(i)]=boss(j);
}

int main()
{
	cin>>n>>m;
	//------sorteaza muchiile
	for(int i=1;i<=m;i++)
		{
			cin>>a[i]>>b[i]>>cost[i];
			point[i]=i;
		}
	
	sort(point+1,point+m+1,f); //pointeaza la muchiile sortate crescator
	//------
	
	//------gaseste muchiile care formeaza arborele
	for(int i=1;i<=n;i++) MD[i]=i;
	
	for(int i=1;i<=m;i++)
		{
			if(boss(a[point[i]])!=boss(b[point[i]]))
				{
					res+=cost[point[i]];
					uneste(a[point[i]],b[point[i]]);
					R.push_back(point[i]);
				}
		}
	//------
	
	//------afiseaza rezultatele
	cout<<res<<endl;
	cout<<n-1<<endl;
	for(int i=0;i<n-1;i++)
		cout<<a[R[i]]<<' '<<b[R[i]]<<'\n';
	//------
}