#include <algorithm>
#include <stdio.h>
#include <vector>

#define pb push_back
#define f first
#define s second
#define mp make_pair

using namespace std;

int N, M, T[200010];
vector <pair <int, int> > Sol;
vector <pair <int, pair <int, int> > > L;

int Rad(int nod)
{
	if (T[nod] != nod)
        T[nod] = Rad(T[nod]);

	return T[nod];
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);

		L.pb(mp(c, mp(x, y)));
	}

	sort(L.begin(), L.end());

	for (int i = 0; i <= N; i++)
		T[i]=i;

	int Cost = 0;

	for (int i = 0; i < M; i++)
	{
        int n1 = L[i].s.f, n2 = L[i].s.s;

		if (Rad(n1) != Rad(n2))
		{
			Cost += L[i].f;
			Sol.pb(mp(n1, n2));
			T[T[n2]] = T[n1];
		}
	}

	printf("%d\n", Cost);
	printf("%d\n", Sol.size());
	for (int i = 0; i < Sol.size(); i++)
		printf("%d %d\n", Sol[i].f, Sol[i].s);

	return 0;
}