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

#define NMAX 200001
#define MMAX 400001
#define mp make_pair
#define pb push_back
#define x first
#define y second

vector < pair < int , pair < int , int > > > v;
vector < pair < int , int > > sol;
int rang[NMAX],p[NMAX];

int multime(int x)
{
	int r,y;
	r=x;
	while(r!=p[r])
		r=p[r];
	while(x!=p[x]) {
		y=p[x];
		p[x]=r;
		x=y;
	}
	return r;
}

void reuneste(int x, int y) 
{
	x=multime(x);
	y=multime(y);
	if(rang[x]<rang[y])
		p[x]=y;
	else p[y]=x;
	if(rang[x]==rang[y])
		rang[x]++;
}

int main ()
{
	int n,m,i,ct,x,y,cost,k;
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		v.pb( mp ( cost , mp(x,y) ) );
	}
	f.close();
	sort(v.begin(),v.end());
	for(i=1;i<=n;i++) {
		p[i]=i;
		rang[i]=1;
	}
	ct=0;
	for(i=0,k=0;i<=m-1 && k<=n-2;i++) 
		if(multime(v[i].y.x)!=multime(v[i].y.y)) {
			reuneste(v[i].y.x,v[i].y.y);
			ct=ct+v[i].x;
			k++;
			sol.pb(mp(v[i].y.x,v[i].y.y));
		}
	g<<ct<<'\n'<<n-1<<'\n';
	for(i=0;i<=n-2;i++)
		g<<sol[i].x<<" "<<sol[i].y<<'\n';
	g.close();
	return 0;
}