# include <fstream>
# include <climits>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
const int maxn = 10000;

int a[maxn][maxn],n,m;

void prim(int r)
{
	int i, cheie[maxn], p[maxn], radacina, vizitati[maxn];
	radacina = r;
	for (i = 1; i <= n; i++)
	{
		cheie[i] = INT_MAX;
		p[i] = 0;
		vizitati[i] = 0;
	}
	vizitati[r] = 1;

	int K = 1,suma=0,minim;
	int minim_nevizitat, indice_nevizitat;
	while (K < n)
	{
		minim = INT_MAX;
		minim_nevizitat = INT_MAX;
		indice_nevizitat = 0;
		for (i = 1; i <= n; i++)
			if (vizitati[i] == 0 && cheie[i] < minim_nevizitat)
			{
				minim_nevizitat = cheie[i];
				indice_nevizitat = i;
			}
		for (i = 1; i <= n; i++)
			if (a[r][i] != INT_MAX )
			{
				if (a[r][i] < cheie[i] && vizitati[i]==0)
				{
					p[i] = r;
					cheie[i] = a[r][i];
					if (cheie[i] < minim_nevizitat)
					{
						minim_nevizitat = cheie[i];
						indice_nevizitat = i;
						//minim = cheie[i];
						//nod_bun = i;
					}
				}
			}
		
		

		r = indice_nevizitat;
		vizitati[r] = 1;
		suma += minim_nevizitat;
		K++;
	}

	g << suma << "\n";
	g << n - 1 << "\n";
	for (i = 1; i <= n; i++)
		if (p[i] != 0)
			g << i << " " << p[i] << "\n";
}
int main()
{
	
	f >> n >> m;
	int i,j,x,y,z;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			a[i][j] = INT_MAX;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> z;
		a[x][y] = a[y][x] = z;
	}
	prim(1);
}