#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

vector <pair < int, pair <int, int> > > v[200005];
vector <pair < int, pair <int, int> > > :: iterator it;
priority_queue <
	pair <int, pair <int, int> > ,
	vector < pair <int, pair <int, int> > >,
	greater < pair <int, pair <int, int> > >
	> q;
pair <int, pair <int, int> > currElement;
bool viz[200005];
int r[200005][2];
int i, j, n, m, x, y, c, rt, totalCost;

int main(){
	f>>n>>m;
	for (i=1; i<=m; i++){
		f>>x>>y>>c;
		v[x].push_back (make_pair(c, make_pair (x, y) ));
		v[y].push_back (make_pair(c, make_pair (y, x) ));
	}
	
	for (it=v[1].begin(); it!=v[1].end(); it++){
		q.push(*it);
	}
	viz[1]=1;
	
	for (i=1; i<n; i++){
		do {
			currElement=q.top();
			q.pop();
		} while (viz[currElement.second.second]==1);
		viz[currElement.second.second]=1;
		
		totalCost+=currElement.first;
		x=currElement.second.first;
		y=currElement.second.second;
		r[i][0]=x;
		r[i][1]=y;
		
		for (it=v[y].begin(); it!=v[y].end(); it++){
			if (viz[(*it).second.second]==0) q.push(*it);
		}
	}
	
	g<<totalCost<<"\n"<<n-1<<"\n";
	for (i=1; i<n; i++){
		g<<r[i][0]<<" "<<r[i][1]<<"\n";
	}
}