#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using std::vector;
using std::string;
struct Muchie {
	int first, second;
	long long third;
};

bool Compare(Muchie a, Muchie b) {
	return a.third < b.third;
}

int root(int k,vector<int>& T) {
	
	if (T[k] == k)
		return k;
	return T[k] = root(T[k],T);
}

void Union(int x, int y, vector<int>& T, vector<int>& R) {

	if (R[x] > R[y])
		T[y] = x;
	else {
		T[x] = y;
		if (R[x] == R[y])
			R[y]++;
	}
}

void citire(const string& in, int& n, int& m, vector<Muchie>& M) {
	std::ifstream f;
	f.open(in);
	f >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		long long c;
		f >> x >> y >> c;
		M.push_back({ x,y,c });
	}

	f.close();
}

void Kruskal(int n, int m, vector<Muchie>& M, vector<int>& T, vector<int>& R, vector<std::pair<int, int>>& sol, long long& cost) {

	sort(M.begin(), M.end(), Compare);

	for (vector<Muchie>::iterator it = M.begin(); it != M.end(); it++) {

		int x = root(it->first,T);
		int y = root(it->second,T);
		if (T[x] != T[y]) {
			Union(x, y,T,R);
			cost += it->third;
			sol.push_back(std::make_pair(it->first, it->second));
		}
	}

}

int main(int argc, char* argv[]) {

	string in = "apm.in";
	string out = "apm.out";

	int n, m;
	vector<Muchie> M;
	vector<std::pair<int, int> > sol;
	long long cost=0;
	citire(in, n, m, M);
	vector<int> T,R;
	T.resize(n + 5);
	R.assign(n + 5, 1);
	for (int i = 1; i <= n; i++)
		T[i] = i;
	Kruskal(n, m, M, T, R, sol, cost);
	std::ofstream g;
	g.open(out);
	g << cost << "\n";
	g << sol.size() << "\n";
	for (vector<std::pair<int, int> >::iterator it = sol.begin(); it != sol.end(); it++) {
		g << it->first << " " << it->second << "\n";
	}
	
	g.close();
	return 0;
}