#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fs first
#define sc second
int x,y,z,rs,n,k,GR[200010];
priority_queue<pair<int,pair<int,int>>> s;
//vector<pair<int,int>> v[200010];
pair<int,int>u[200010];

int Cauta(int x)
{
	if(GR[x]==x) return x;
	GR[x]=Cauta(GR[x]);
	return GR[x];
}
void Unire(int x, int y)
{
	GR[Cauta(x)]=Cauta(y);
}
int main()
{
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		cin>>x>>y>>z;
		s.push({-z,{x,y}});
	}
	for(int i=1;i<=n;i++) GR[i]=i;
	k=1;
	while(k<n)
	{
		x=Cauta(s.top().sc.fs);
		y=Cauta(s.top().sc.sc);
		z=s.top().fs;
		if(x!=y)
		{
			rs+=-z;
			u[k].fs=s.top().sc.fs;
			u[k].sc=s.top().sc.sc;
			Unire(x,y);
			k++;
		}
		s.pop();
	}
	cout<<rs<<"\n"<<n-1<<"\n";
	for(int i=1;i<n;i++) cout<<u[i].fs<<" "<<u[i].sc<<"\n";
}