#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <queue>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <bitset>
#include <stack>

using namespace std;

#define pb			push_back
#define mp			make_pair
#define all(v)			v.begin(), v.end()
#define ff			first
#define ss			second
#define pii			pair<int,int>
#define maxM			400100
#define maxN			200100

struct g {
	int A, B, Cost;
};
vector< g > Muchie;
vector< pii > Sol;
int N, M, CostFinal, comp[maxN];

bool cmp(g a, g b) {
	return a.Cost < b.Cost;
}

#ifdef DEBUG
void print () {
	int i;
	for (i = 1; i <= N; ++ i)	fprintf(stderr, "%d ", comp[i]);
	fprintf(stderr, "\n");
}
#endif
int grupa(int x){
#ifdef DEBUG
	print();
#endif
	if (comp[x] == x)	return x;
	comp[x] = grupa(comp[x]);
	return comp[x];
}

void Uneste(int a, int b) {
	comp[grupa(a)] = grupa(b);
}

void Apm() {
	int i;
	for (i = 1; i <= N; ++ i)	comp[i] = i;
	
	for (i = 0; i < M; ++ i) {
	#ifdef DEBUG
		fprintf(stderr, "%d %d\n", Muchie[i].A, Muchie[i].B);
	#endif
		if (grupa(Muchie[i].A) == grupa(Muchie[i].B)) {
			Uneste(Muchie[i].A, Muchie[i].B);fprintf(stderr, "*");
			Sol.pb( mp(Muchie[i].A, Muchie[i].B) );fprintf(stderr, "*");
			CostFinal += Muchie[i].Cost;fprintf(stderr, "*");
		}
	}
}

int main() {
	int i;
	g now;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	
	for (scanf("%d%d", &N, &M), i = 1; i <= M; ++ i) {
		scanf("%d%d%d", &now.A, &now.B, &now.Cost);
		Muchie.pb(now);
	}
	
	sort(all(Muchie), cmp);
#ifdef DEBUG
	for (i = 0; i < M; ++ i)	printf("%d %d %d\n", Muchie[i].A, Muchie[i].B, Muchie[i].Cost);
#endif
	Apm();	
	
	cout << CostFinal << "\n" << Sol.size() << "\n";
	for (i = 0; i < Sol.size(); ++ i)
		printf("%d %d\n", Sol[i].ff, Sol[i].ss);
}