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

#include <cstdlib>

using namespace std;

const int MAX_N = 200005;
const int MAX_M = 400005;

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

struct Edge {
	int a, b, cost;

	friend istream& operator >> (istream &in, Edge &e) {
		return in >> e.a >> e.b >> e.cost;
	}
	friend ostream& operator << (ostream &out, Edge &e) {
		return out << e.a << " " << e.b;
	}

	bool operator < (const Edge &e) const {
		return cost < e.cost;
	}
};

int n, m;
Edge v[MAX_M];
int t[MAX_N];
int apmCost = 0;
vector<Edge> apm;

inline int find(int a) {
	return a == t[a] ? a : t[a] = find(t[a]);
}

inline void merge(int a, int b) {
	if (rand() & 1) t[a] = b;
	else t[b] = a;
}

int main() {
	// Read
	fin >> n >> m;
	for (int i = 0; i < m; ++i)
		fin >> v[i];

	// Solve
	sort(v, v + m);
	for (int i = 1; i <= n; ++i)
		t[i] = i;

	for (Edge *ptr = v; ptr != v + m; ++ptr)
		if (find(ptr->a) != find(ptr->b)) {
			merge(find(ptr->a), find(ptr->b));
			apmCost += ptr->cost;
			apm.push_back(*ptr);
		}
	
	// Write
	fout << apmCost << "\n" << n-1 << "\n";
	for (vector<Edge>::iterator it = apm.begin(); it != apm.end(); ++it)
		fout << *it << "\n";
}