#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
struct nod {
	int x,y,cost;
	inline nod ( int _x, int _y, int _cost) {
		x=_x;
		y=_y;
		cost=_cost;
	}
	inline bool operator < (const nod &c) const {
		return cost>c.cost;
	}
};
vector <nod> v[200001],a;
priority_queue <nod> c;
bitset <200001> d;
int main ()
{
	int n,m,x,y,cost,i,sum;
	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(nod(x,y,cost));
		v[y].push_back(nod(y,x,cost));
	}
	f.close();
	for(vector <nod> :: iterator it=v[1].begin();it!=v[1].end();it++) 
		c.push(nod(it->x,it->y,it->cost));
	d[1]=1;
	sum=0;
	for(i=2;i<=n;i++) {
		while(d[c.top().x]!=1 || d[c.top().y]!=0 )
			c.pop();
		a.push_back(nod(c.top().x,c.top().y,0));
		sum=sum+c.top().cost;
		y=c.top().y;
		d[y]=1;
		c.pop();
		for(vector <nod> :: iterator it=v[y].begin();it!=v[y].end();it++)
			if(d[it->y]==0)
				c.push(nod(y,it->y,it->cost));
	}
	g<<sum<<'\n'<<a.size()<<'\n';
	for(vector <nod> :: iterator it=a.begin();it!=a.end();it++)
		g<<it->x<<" "<<it->y<<'\n';
	g.close();
	return 0;
}