#include<iostream>
#include<fstream>
#include<queue>
#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;
	}
	bool operator < (const muchie &c) const {
		return cost>c.cost;
	}
};

vector <muchie> v[NMAX],sol;
priority_queue <muchie> s;
int viz[NMAX];

int main ()
{
	int n,m,i,x,y,cost,cmin;
	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(muchie(x,y,cost));
		v[y].push_back(muchie(y,x,cost));
	}
	f.close();
	cmin=0;
	for(vector <muchie> :: iterator it=v[1].begin();it!=v[1].end();it++)
		s.push(muchie(1,it->y,it->cost));
	viz[1]=1;
	for(i=1;i<=n-1;i++) {
		while(viz[s.top().x]==0 || viz[s.top().y]==1)
			s.pop();
		sol.push_back(muchie(s.top().x,s.top().y,s.top().cost));
		cmin=cmin+s.top().cost;
		y=s.top().y;
		s.pop();
		for(vector <muchie> :: iterator it=v[y].begin();it!=v[y].end();it++)
			if(viz[it->y]==0)
				s.push(muchie(y,it->y,it->cost));
		viz[y]=1;
	}
	g<<cmin<<'\n'<<n-1<<'\n';
	for(vector <muchie> :: iterator it=sol.begin();it!=sol.end();it++)
		g<<it->x<<" "<<it->y<<'\n';
	g.close();
	return 0;
}