# include <cstdio>
# include <algorithm>

using namespace std;

class muchie
{
public:
	int x, y, c;
	bool operator< (const muchie& other) const
	{
		return c<other.c;
	}

} M[400005], sol[200005];

int tt[200005], h[200005];
int cost, poz, n, m, rad1, rad2, i, j;

int find(int x)
{
	int rad = x, aux;
	while (tt[rad] != 0)
		rad = tt[rad];
	while (tt[x] != rad&&tt[x] != 0)
	{
		aux = tt[x];
		tt[x] = rad;
		x = aux;
	}
	return rad;
}

void UNION(int rad1, int rad2)
{
	if (h[rad1]<h[rad2])
		tt[rad1] = rad2;
	else
	{
		tt[rad2] = rad1;
		if (h[rad1] == h[rad2])
			h[rad1]++;
	}
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++)
		scanf("%d%d%d", &M[i].x, &M[i].y, &M[i].c);
	sort(M + 1, M + m + 1);
	poz = 1;
	for (i = 1; i<n; i++)
	{
		rad1 = find(M[poz].x);
		rad2 = find(M[poz].y);
		while (rad1 == rad2)
		{
			poz++;
			rad1 = find(M[poz].x); rad2 = find(M[poz].y);
		}
		sol[i] = M[poz]; cost += M[poz].c;
		UNION(rad1, rad2);
	}
	printf("%d\n%d\n", cost, n - 1);
	for (i = 1; i <= n - 1; i++)
		printf("%d %d\n", sol[i].x, sol[i].y);
	return 0;
}