#include <iostream>
#include <fstream>

using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

#define N 400000

struct muchii{

	int x, y, cost;
};

muchii G[N + 1];
int k, A[N + 1], c[N + 1];

void poz(int li, int ls, int& k, muchii G[N + 1])
{

	int i = li, j = ls, i1 = 0, j1 = -1, c;
	muchii b;
	while (i < j)
	{
		if (G[i].cost > G[j].cost)
		{
			b = G[i];
			G[i] = G[j];
			G[j] = b;
			c = i1;
			i1 = -j1;
			j1 = -c;
		}
		i += i1;
		j += j1;
	}
	k = i;
}

void quicksort(int li, int ls)
{
	if (li < ls)
	{
		poz(li, ls, k, G);
		quicksort(li, k - 1);
		quicksort(k + 1, ls);
	}
}

int main()
{
	int n, m, i, j, s = 0, min, max;
	fi >> n >> m;
	for (i = 1; i <= m; i++)
		fi >> G[i].x >> G[i].y >> G[i].cost;
	for (i = 1; i <= n; i++)
		c[i] = i;
	int Nrm = 0;
	quicksort(1, m);
	for (i = 1; Nrm < n - 1; i++)
	{
		if (c[G[i].x] != c[G[i].y])//daca nu e ciclu
		{
			A[++Nrm] = i;
			if (c[G[i].x] < c[G[i].y])
			{
				max = c[G[i].y];
				min = c[G[i].x];
			}
			else
			{
				min = c[G[i].y];
				max = c[G[i].x];
			}
			s += G[i].cost;
			for (j = 1; j <= n; j++)
				if (c[j] == max) c[j] = min;
		}
	}
	fo << s << "\n" << Nrm<<"\n";
	for (i = 1; i <= Nrm; i++)
		fo << G[A[i]].x << " " << G[A[i]].y << "\n";




}