#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fs first
#define sc second
int x,y,z,x1,y2,z1,rs,mi,n,k,viz[200010];
priority_queue<pair<int,pair<int,int>>> s;
vector<pair<int,int>> v[200010];
pair<int,int>u[200010];
int main()
{
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	cin>>n>>k;
	mi=20000;
	for(int i=1;i<=k;i++)
	{
		cin>>x>>y>>z;
		v[x].pb({y,z});
		v[y].pb({x,z});
		if(z<mi) z1=z,x1=x,y2=y,mi=z;
	}
	for(auto it:v[x1]) s.push({-it.sc,{x1,it.fs}});
	viz[x1]=1;
	for(int i=1;i<n;i++)
	{
		while(viz[s.top().sc.fs]&&viz[s.top().sc.sc]) s.pop();
		z=-s.top().fs;
		x=s.top().sc.fs;
		y=s.top().sc.sc;
		u[i].fs=x;
		u[i].sc=y;
		viz[y]=1;
		rs+=z;
		s.pop();
		for(auto it:v[y]) if(!viz[it.fs])s.push({-it.sc,{y,it.fs}});
	}
	cout<<rs<<"\n"<<n-1<<"\n";
	for(int i=1;i<n;i++) cout<<u[i].fs<<" "<<u[i].sc<<"\n";

}