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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int maxn = 400100;

int parinte[maxn], X[maxn], Y[maxn], C[maxn];
int N, M, ANS, IND[maxn];
vector<pair<int, int>> add;

//struct str {
//	int s, d, cost;
//};
//
//struct less_than_key
//{
//	inline bool operator() (const str& struct1, const str& struct2)
//	{
//		return (struct1.cost > struct2.cost);
//	}
//};
//
//priority_queue<str, vector<str>, less_than_key> q;

int find(int i) {
	if (parinte[i] == i) return i;
	parinte[i] = find(parinte[i]);
	return parinte[i];
}

void Union(int i, int j) {

	int radacinaI = find(i);
	int radacinaJ = find(j);

	if (radacinaI != radacinaJ) {
		parinte[radacinaI] = radacinaJ;
	}
}

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


int main() {


	fin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		fin >> X[i] >> Y[i] >> C[i];
		IND[i] = i;
	}
	for (int i = 1; i <= N; ++i) parinte[i] = i;
	sort(IND + 1, IND + M + 1, cmpf);//sortam muchiile dupa cost

	for (int i = 1; i <= M; ++i) {

		if (find(X[IND[i]]) != find(Y[IND[i]])) {
			ANS += C[IND[i]];
			add.push_back({ X[IND[i]], Y[IND[i]] });
			Union(X[IND[i]], Y[IND[i]]);
		}
	}
	fout << ANS << "\n";
	fout << add.size() << "\n";
	for (int i = 0; i < add.size(); ++i)
		fout << add[i].first << " " << add[i].second << "\n";

	return 0;
}