#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 200005;
const int MMAX = 400005;
struct ABC
{
	int x, y;
	int cost;
};
struct SOLUTIE
{
	int x, y;
};
SOLUTIE sol[NMAX];
ABC v[MMAX];
int t[NMAX];
int h[NMAX];
bool cmp(ABC first, ABC second)
{
	return first.cost < second.cost;
}
int FindSet(int x)
{
	if(t[x] == x)
		return x;
	return FindSet(t[x]);
}
void UnionSet(int x, int y)
{
	if(h[x] == h[y]) {
		++h[x];
		t[y] = x;
	}
	else if(h[x] > h[y]) {
		t[y] = x;
	}
	else {
		t[x] = y;
	}
}

int main()
{
    int n, m, i, x, y, sol1 = 0, k = 0;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d", &n, &m);
    for(i = 1;i <= n; ++i) {
		t[i] = i;
		h[i] = 1;
    }
    for(i = 1;i <= m; ++i) {
		scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
    }
    sort(v + 1, v + m + 1, cmp);
    for(i = 1;i <= m; ++i) {
		x = FindSet(v[i].x);
		y = FindSet(v[i].y);
		if(x != y) {
			UnionSet(x, y);
			sol1 += v[i].cost;
			sol[++k].x = v[i].x;
			sol[k].y = v[i].y;
		}
    }
    printf("%d\n%d\n", sol1, k);
    for(i = 1;i <= k; ++i) {
		printf("%d %d\n", sol[i].x, sol[i].y);
    }
    return 0;
}