#include<stdio.h>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

typedef struct muchie {
	int x, y;
	int distance;
}muchie;

int n, m;

muchie a[100000];
int r[10000];
int t[10000];

void unify(int x, int y)
{
	if (r[x] > r[y])
	{
		t[x] = y;
	}
	else
	{
		t[y] = x;
	}

	if (r[x] == r[y])
	{
		r[x]++;
	}
}

int functie(muchie a, muchie b)
{
	return a.distance < b.distance ? 1 : 0;
}

int found(int x)
{
	while (t[x] != x)
	{
		x = t[x];
	}

	return x;
}

int s = 0;

vector<muchie> result(0);

void display()
{
	printf("%d\n", s);
	printf("%d\n", result.size());
	for (int i = 0; i < result.size(); i++)
	{
		printf("%d %d\n", result[i].x, result[i].y);
	}
}
int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d", &n);
	scanf("%d", &m);

	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].distance);
		r[i] = 1;
		t[i] = i;
	
	}
	sort(a + 1, a + m + 1, functie);

	for (int i = 1; i <= m; i++)
	{
		if (found(a[i].x) != found(a[i].y))
		{
			unify(found(a[i].x), found(a[i].y));
			result.push_back(a[i]);
			s += a[i].distance;
		}
	}


	display();
	return 0;
}