#include <cstdio>
#include <vector>
#define NMAX 200001
#define MMAX 400001
#define inf 1000000000
using namespace std;
FILE *fin=fopen("apm.in", "r");
FILE *fout=fopen("apm.out", "w");

void citire();
void afisare();
void Prim();

struct varf
{
	int x, c;
};

int n, m, start;
vector<varf> G[NMAX];
int cmin[NMAX];
int prec[NMAX];
bool sel[NMAX];

int main()
{
	citire();
	Prim();
	afisare();
	return 0;
}

void citire()
{
	varf aux;
	int i, x, y, cost;
	fscanf(fin, "%d %d", &n, &m);
	start=1;
	for (i=0; i<m; i++)
	{
		fscanf(fin, "%d %d %d", &x, &y, &cost);
		aux.x=y;
		aux.c=cost;
		G[x].push_back(aux);
		aux.x=x;
		G[y].push_back(aux);
	}
	sel[start]=1;
	for (i=1; i<=n; i++) cmin[i]=inf;
	cmin[start]=0;
	for (i=0; i<G[start].size(); i++)
	{
		cmin[G[start][i].x]=G[start][i].c;
		prec[G[start][i].x]=start;
	}
}

void Prim()
{
	int i, j, minim, vfmin;
	for (i=0; i<n-1; i++)
	{
		minim=inf+1;
		for (j=1; j<=n; j++)
		{
			if (!sel[j]&&cmin[j]<minim)
			{
				minim=cmin[j];
				vfmin=j;
			}
		}
		sel[vfmin]=1;
		for (j=0; j<G[vfmin].size(); j++)
		{
			if (!sel[G[vfmin][j].x]&&cmin[G[vfmin][j].x]>G[vfmin][j].c)
			{
				cmin[G[vfmin][j].x]=G[vfmin][j].c;
				prec[G[vfmin][j].x]=vfmin;
			}
		}
	}
}

void afisare()
{
	int i, S=0;
	for (i=1; i<=n; i++) S+=cmin[i];
	fprintf(fout, "%d\n%d\n", S, n-1);
	for (i=1; i<=n; i++) if (i!=start) fprintf(fout, "%d %d\n", i, prec[i]);
}