#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int find(int x);
void group(int x, int y);
void solve();
void init();
bool cmp(int a, int b);

const int maxn = 200200;

int N, M;
int X[maxn], Y[maxn], C[maxn], IND[maxn], SET[maxn], RG[maxn], sol, SOL[maxn], l;



int main()
{
	init();
	solve();
	return 0;
}


int find(int x)
{
	int R, y;
	for (R = x; R != SET[R];R = SET[R]);
	while (SET[x] != x)
	{
		y = SET[x];
		SET[x] = R;
		x = y;
	}

	return R;
}

void group(int x, int y)
{
	if (RG[x] > RG[y])
		SET[y] = x;
	else SET[x] = y;

	if (RG[x] == RG[y]) RG[y]++;
}

void init()
{
	fi >> N >> M;
	for (int i = 1;i <= M;i++)
	{
		fi >> X[i] >> Y[i] >> C[i];
		IND[i] = i;
	}
	for (int i = 1;i <= N;i++)
	{
		SET[i] = i;
		RG[i] = 1;
	}

	sort(IND + 1, IND + M + 1, cmp);
}

bool cmp(int a, int b)
{
	return C[a] < C[b];
}

void solve()
{
	for (int i = 1;i <= M;i++)
	{
		if (find(X[IND[i]]) != find(Y[IND[i]]))
		{
			sol += C[IND[i]];
			group(find(X[IND[i]]), find(Y[IND[i]]));
			SOL[++l] = IND[i];
		}
	}
	fo << sol << '\n' << N - 1 << '\n';
	for (int i = 1;i < N;i++)
		fo << X[SOL[i]] << " " << Y[SOL[i]] << '\n';
}