#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct muchie{
	int a, b, cost;
};

const int nmax = 200006;
int n, m, vradacina[nmax], rang[nmax], rasp, lrasp;
muchie v[2 * nmax], vrasp[nmax];

int compar(muchie a, muchie b)
{
	return a.cost<b.cost;
}

int find_radacina(int x)
{
	if(vradacina[x]==0)
	{
		return x;
	}
	else
	{
		return (vradacina[x] = find_radacina(vradacina[x]));
	}
}

int main(){
	int player_unu=0;

	in>>n>>m;
	for(int i = 1; i<=n; i++)
		rang[i]++;
	for(int i = 1; i<=m; i++)
	{
		in>>v[i].a>>v[i].b>>v[i].cost;
	}

	sort(v + 1, v + 1 + m, compar);

	for(int i = 1; i<=m; i++)
	{
		int rada = find_radacina(v[i].a), radb = find_radacina(v[i].b);

		if(rada!=radb)
		{
			rasp += v[i].cost;

			vrasp[lrasp] = v[i];
			lrasp++;

			if(rang[rada]<rang[radb])
			{
				vradacina[rada] = radb;
				rang[radb] += rang[rada];
			}
			else
			{
				vradacina[radb] = rada;
				rang[rada] += rang[radb];
			}
		}
	}

	out<<rasp<<'\n'<<lrasp<<'\n';
	for(int i = 0; i<lrasp; i++)
		out<<vrasp[i].a<<' '<<vrasp[i].b<<'\n';

	return player_unu;
}