#include<iostream>
#include<fstream>
#include<set>
#include<vector>
using namespace std;

#define NMAX 200001
#define MMAX 400001

struct muchie {
	int x,y,cost;
	muchie (int _x, int _y, int _cost) {
		x=_x;
		y=_y;
		cost=_cost;
	}
};

struct cmp {
	bool operator() (const muchie &a, const muchie &b) const {
		if(a.cost==b.cost)
			return a.x<b.x;
		return a.cost<b.cost;
	}
};

vector < pair <int, int> > v[NMAX],sol;
set <muchie,cmp> s;
int viz[NMAX];

int main ()
{
	int n,m,i,x,y,cost,cmin;
	muchie a(0,0,0);
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		v[x].push_back(make_pair(y,cost));
		v[y].push_back(make_pair(x,cost));
	}
	f.close();
	cmin=0;
	for(vector < pair <int, int> > :: iterator it=v[1].begin();it!=v[1].end();it++)
		s.insert(muchie(1,it->first,it->second));
	viz[1]=1;
	for(i=1;i<=n-1;i++) {
		while(viz[(*s.begin()).x]!=1 || viz[(*s.begin()).y]!=0)
			s.erase(s.begin());
		a=*(s.begin());
		s.erase(s.begin());
		cmin=cmin+a.cost;
		sol.push_back(make_pair(a.x,a.y));
		viz[a.y]=1;
		for(vector < pair <int, int> > :: iterator it=v[a.y].begin();it!=v[a.y].end();it++)
			if(viz[it->first]==0) 
				s.insert(muchie(a.y,it->first,it->second));
	}
	g<<cmin<<'\n'<<n-1<<'\n';
	for(vector < pair <int, int> > :: iterator it=sol.begin();it!=sol.end();it++)
		g<<it->first<<" "<<it->second<<'\n';
	g.close();
	return 0;
}