#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector<vector<int>> nSets;

void constructSet(int n) {
	for(int i=1; i<=n; i++)
	{
		vector<int> set; set.push_back(i);
		nSets.push_back(set);
	}
}
vector<int> union_(vector<int> x, vector<int> y) {
	vector<int> r(x);
	for (int item : y) {
		if (find(r.begin(), r.end(), item) == r.end()) r.push_back(item);
	}
	return r;
}
vector<int> find_(int x) {
	vector<int> result;
	for (vector<vector<int>>::iterator it = nSets.begin(); it != nSets.end(); it++) {
		if (find(it->begin(), it->end(), x) != it->end()) {
			result = *it;
			nSets.erase(it);
			return result;
		}
	}
	return vector<int>();
}
bool isEquals(vector<int> x, vector<int> y) {
	for (int val : y)
		if (find(x.begin(), x.end(), val) == x.end()) return false;
	return true;
}
struct Muchie {
	int x, y, val;
	bool operator<(Muchie& edge) {
		return this->val < edge.val;
	}
	friend std::istream& operator>>(std::istream& in, Muchie& edge) {
		in >> edge.x >> edge.y >> edge.val;
		return in;
	}
	friend std::ostream& operator<<(std::ostream& out, const Muchie& edge) {
		out << edge.y << " " << edge.x;
		return out;
	}
};

struct Graf {
	int n, m;
	vector<Muchie> vMuchii;
};

Graf Citire() {
	Graf myGraf;
	fin >> myGraf.n >> myGraf.m;
	for (int i = 0; i < myGraf.m; i++)
	{
		Muchie* edge = new Muchie;
		fin >> *edge;
		myGraf.vMuchii.push_back(*edge);
	}
	return myGraf;
}
vector<Muchie> Kruskal(int n, int& cost, vector<Muchie> vMuchii) {
	constructSet(n); cost = 0;
	make_heap(vMuchii.begin(), vMuchii.end());
	sort_heap(vMuchii.begin(), vMuchii.end());
	vector<Muchie> result;
	while (nSets.size() != 1) {
		Muchie edge = vMuchii.front(); vMuchii.erase(vMuchii.begin());
		auto x = find_(edge.x), y = find_(edge.y);
		if (!isEquals(x, y))
		{
			result.push_back(edge); cost += edge.val;
			nSets.push_back(union_(x, y));
		}
		else {
			if(!x.empty()) nSets.push_back(x);
			if(!y.empty()) nSets.push_back(y);
		}
	}
	return result;
}


int main() {
	auto graf = Citire(); int cost;
	auto result = Kruskal(graf.n, cost, graf.vMuchii);
	fout << cost << endl;
	fout << result.size() << endl;
	for (Muchie edge : result) {
		fout << edge << endl;
	}
	return 0;
}