#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200000
#define f first
#define s second

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, tata[NMAX+10], rang[NMAX+10], ans;
vector <pair <int, int> > sol;

struct Kruskal
{	int n1, n2, c;	
}K[2*NMAX+10];

bool mycmp(Kruskal a, Kruskal b)
{	return a.c < b.c;
}

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

void unite(int x, int y)
{	if(rang[x] < rang[y])
		tata[x] = y;
	else
		tata[y] = x;
	if(rang[x] == rang[y])
		rang[x]++;
}

int main()
{
	fin >> n >> m;
	for(int i=1; i<=m; i++)
		{	int nod1, nod2, cost;
			fin >> nod1 >> nod2 >> cost;
			K[i] = {nod1, nod2, cost};
		}
	sort(K+1, K+m+1, mycmp);
	for(int i=1; i<=n; i++)
		{	tata[i] = i;
			rang[i] = 1;
		}
	for(int i=1; i<=m; i++)
		{	int val1 = findDaddy(K[i].n1), val2 = findDaddy(K[i].n2);
			if(val1 == val2)
				continue;
			unite(val1, val2);
			sol.push_back({val1, val2});
			ans += K[i].c;
		}
	fout << ans << '\n' << n - 1 << '\n';
	for(auto u : sol)
		fout << u.f << ' ' << u.s << '\n';
	return 0;
}