#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int maxn = 400100;
vector<vector<int>>ls, apm;
int r[maxn];



int main() {

	int n, m, k = 0, total = 0;
	in >> n >> m;
	while (m--) {
		int v1, v2, c;
		in >> v1 >> v2 >> c;
		r[v1] = v1;
		r[v2] = v2;
		ls.push_back({ c,v1,v2 });
		k++;
	}

	sort(ls.begin(), ls.end());

	for (auto muchie : ls)
	{
		int nod1 = muchie[1];
		int nod2 = muchie[2];
		int cost = muchie[0];
		if (r[nod1] != r[nod2]) {
			total += cost;
			cout << nod1 << " " << nod2 << "\n";
			int r1 = r[nod1];
			int r2 = r[nod2];
			for (int i = 1; i <= n; i++)
			{
				
				if (r[i] == r2)
					r[i] =r1 ;
				cout << r[i] << " ";
			}cout << "\n";
			apm.push_back({ nod1,nod2 });
		}
	}
	out << total << "\n" << n - 1 << "\n";
	for (auto x : apm) {
		out << x[0] << " " << x[1] << "\n";
	}

	return 0;
}