#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back

using namespace std;

const int maxn = 400100;

int GR[maxn], X[maxn], Y[maxn], C[maxn];
int N, M, ANS, IND[maxn];
vector<int> VANS;

int grupa(int i)
{
	if (GR[i] == i) return i;
	GR[i] = grupa(GR[i]);
	return GR[i];
}

void reuniune(int i, int j)
{
	GR[grupa(i)] = grupa(j);
}

bool cmpf(int i, int j)
{
	return(C[i] < C[j]);
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d\n", &N, &M);
	for (int i = 1; i <= M; ++i)
	{
		scanf("%d %d %d\n", &X[i], &Y[i], &C[i]);
		IND[i] = i;
	}

	for (int i = 1; i <= N; ++i) GR[i] = i;
	for (int i = 1; i <= N; ++i) GR[i] = i;
	sort(IND + 1, IND + M + 1, cmpf);
	for (int i = 1; i <= M; ++i)
	{
		if (grupa(X[IND[i]]) != grupa(Y[IND[i]])) {
			ANS += C[IND[i]]; reuniune(X[IND[i]], Y[IND[i]]);
			VANS.pb(IND[i]);
		}
	}
	printf("%d\n", ANS);
	printf("%d\n", N - 1);
	for (int i = 0; i < N - 1; ++i)
		printf("%d %d\n", X[VANS[i]], Y[VANS[i]]);
	return 0;
}