#include <fstream>
using namespace std;

#define maxn 200001

typedef struct muchie{
	int x,y,cost;};

int t[maxn],n,m,nh;
muchie b[maxn],sol[maxn];

void swap(int x,int y){
	int aux;
	aux=b[x].x;
	b[x].x=b[y].x;
	b[y].x=aux;
	aux=b[x].y;
	b[x].y=b[y].y;
	b[y].y=aux;
	aux=b[x].cost;
	b[x].cost=b[y].cost;
	b[y].cost=aux;}

void sift(int k){
	int son;
	do{
		son=0;
		if(k*2<=nh)
			son=k*2;
		if(k*2+1<=nh&&b[k*2].cost>b[k*2+1].cost)
			son=k*2+1;
		if(b[son].cost>b[k].cost)
			son=0;
		if(son){
			swap(son,k);
			k=son;}}
	while(son);}

void build(){
	nh=m;
	for(int i=nh/2;i>=1;i--)
		sift(i);}

void pop(){
	swap(1,nh);
	nh--;
	sift(1);}

int root(int k){
	while(t[k])
		k=t[k];
	return k;}

int main(){
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	int i,c=0,nr=0;
	for(i=1;i<=m;i++)
		f>>b[i].x>>b[i].y>>b[i].cost;
	build();
	while(nh){
		muchie min;
		min=b[1];
		pop();
		if(root(min.x)!=root(min.y)){
			t[root(min.y)]=root(min.x);
			c=c+min.cost;
			nr++;
			sol[nr]=min;}}
	g<<c<<"\n"<<nr<<"\n";
	for(i=1;i<=nr;i++)
		g<<sol[i].x<<" "<<sol[i].y<<"\n";
	f.close();
	g.close();
	return 0;}