#include <bits/stdc++.h>

using namespace std;

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

int a[400010],b[400010],c[400010],grupa[400010],ind[400010];
int sze[400010];
int ans;
vector<int> ANS;


int Grupa(int i)
{
	if(grupa[i]==i) return i;
	grupa[i]=Grupa(grupa[i]);
	return grupa[i];
}

void unite(int i,int j)
{
	i=Grupa(i);
	j=Grupa(j);
	if(sze[i]<sze[j])
	{
		grupa[i]=j;
		sze[j]+=sze[i];
	}
	else
	{
		grupa[j]=i;
		sze[i]+=sze[j];
	}
}


bool ok(int a,int b)
{
	return (c[a]<c[b]);
}


int main()
{
	int n,m;
	in>>n>>m;
	for(int i=1;i<=m;i++)
	{
		in>>a[i]>>b[i]>>c[i];
		ind[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		grupa[i]=i;
		sze[i]=1;
	}
	sort(ind+1,ind+m+1,ok);
	for(int i=1;i<=m;i++)
	{
		if(Grupa(a[ind[i]])!=Grupa(b[ind[i]]))
		{
			ans+=c[ind[i]];
			unite(a[ind[i]],b[ind[i]]);
			ANS.push_back(ind[i]);
		}
	}
	out<<ans<<"\n";
	out<<n-1<<"\n";
	for(int i=0;i<n-1;i++)
		out<<a[ANS[i]]<<" "<<b[ANS[i]]<<"\n";
	return 0;
}