#include <fstream>
#include <vector>
#define IN "apm.in"
#define OUT "apm.out"
#define NMAX 200001
#define MMAX 400001
#define INF 2000000
using namespace std;

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

struct vecin{int x,c;};

void citire();
void prim();
void afisare();

int n,m;
int cost;
int prv;

vector <vecin> a[NMAX];

int cmin[NMAX], prec[NMAX];
int use[NMAX];

int main()
{
	citire();
	prim();
	afisare();
	fout.close();
	return 0;
}

void prim()
{
	int i, j, x;
	int mm,vm;
	vecin aux;
	for (j=1; j<=n-1; ++j)
	{
		mm=INF;
		vm=INF;
		for (i=2; i<=n; ++i)
			if (use[i]==0 && cmin[i]<mm)
			{
				mm=cmin[i];
				vm=i;
			}
		use[vm]=1;
		
		for (i=0, x=(int)a[vm].size(); i<x; ++i)
		{
			aux=a[vm][i];
			if (cmin[aux.x]>aux.c && !use[aux.x])
			{
				cmin[aux.x]=aux.c;
				prec[aux.x]=vm;
			}
		}
	}
	for (i=1; i<=n; ++i)
		cost+=cmin[i];
}

void afisare()
{
	fout <<cost<<'\n'<<n-1<<'\n';
	
	int i;
	for (i=1; i<=n; ++i)
		if (i!=prv)
			fout <<i<<' '<<prec[i]<<'\n';
}

void citire()
{
	fin >>n>>m;
	
	int i, x, y;
	vecin aux;
	for (i=1; i<=m; ++i)
	{
		fin >>x>>y>>aux.c;
		aux.x=y;
		a[x].push_back(aux);
		
		aux.x=x;
		a[y].push_back(aux);
	}
	
	
	prv=1; use[prv]=1;
	for (i=0, x=(int)a[prv].size(); i<x; ++i)
		cmin[a[prv][i].x]=a[prv][i].c;
	
	for (i=2; i<=n; ++i)
	{
		if (!cmin[i])
			cmin[i]=INF;
		prec[i]=prv;
	}
}