#include <fstream>
#include <algorithm>
#define IN "apm.in"
#define OUT "apm.out"
#define NMAX 400005
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

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

int n, m;
muchie v[NMAX];
int conex[NMAX];
int apm[NMAX], ind;
int cost_total;

void citire();
bool sortare(muchie a,muchie b)
{return a.cost < b.cost;}
void showtime();
void afisare();

int main(int argc, const char * argv[])
{
	citire();
	sort(v+1, v+m+1, sortare);
	showtime();
	afisare();
    return 0;
}

void showtime()
{
	int i, j, k, ma;
	for (i=1; i<=m; ++i)
		if (conex[v[i].x] != conex[v[i].y])
		{
			cost_total+=v[i].cost;
			apm[++ind]=i;
			
			if (conex[v[i].x]<conex[v[i].y])
			{
				k=conex[v[i].x];
				ma=conex[v[i].y];
			}
			else
			{
				ma=conex[v[i].x];
				k=conex[v[i].y];
			}
			for (j=1; j<=n; ++j)
				if (conex[j]==ma)
					conex[j]=k;
		}
}

void afisare()
{
	int i;
	fout <<cost_total<<'\n'<<ind<<'\n';
	for (i=1; i<=ind; ++i)
		fout <<v[apm[i]].x<<' '<<v[apm[i]].y<<'\n';
}

void citire()
{
	fin >>n>>m;
	
	int i;
	for (i=1; i<=m; ++i)
		fin >>v[i].x>>v[i].y>>v[i].cost;
	for (i=1; i<=n; ++i)
		conex[i]=i;
}