#include <iostream>
#include <fstream>
#include <algorithm>
#define  mmax 400005
#define  nmax 200005

using namespace std;

const char iname[] = "apm.in";
const char oname[] = "apm.out";

ifstream fin(iname);
ofstream fout(oname);

int T[nmax], sum;

struct muchie
{
	int capat1;
	int capat2;
	int cost;
}md[mmax];


struct cmp
{
	bool operator()(const muchie &a, const muchie &b)const
	{
		if(a.cost < b.cost)
			return 1;
		return 0;
	}
};

int father(int nod)
{
	if(T[nod] !=  nod)
		T[nod] = father(T[nod]);
	return T[nod];
}
		

int n, m, i, k, sol[mmax];

int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
		fin >> md[i].capat1 >> md[i].capat2 >> md[i].cost;
	sort(md+ 1, md + m + 1, cmp());
	for(i = 1; i <= n; i ++)
		T[i] = i;
	for(i = 1; i <= m; i ++)
	{
		if(father(md[i].capat1) != father(md[i].capat2))
		{
			sum = sum + md[i].cost;
			T[father(md[i].capat1)] = father(md[i].capat2);
			sol[++k] = i;
		}
	}
	fout << sum << "\n";
	fout << k << "\n";
	for(i = 1; i <= k; i ++)
		fout << md[sol[i]].capat1 << " " << md[sol[i]].capat2 << "\n";
	return 0;
}