#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define in "apm.in"
#define out "apm.out"
#define N 200005
#define c first
#define xx second.first
#define yy second.second

typedef pair <int, int> muchie;
typedef pair <int, muchie> arbore;

vector <int> tata (N, 0);
vector <arbore> graf;
vector <muchie> R;
int n, m, sol;

int find (int x) {
	if (tata[x] != x)
		tata[x] = find (tata[x]);
	return tata[x];
}

void unite (int x, int y) {
	tata[x] = y;
}

int main () {
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		graf.push_back (arbore (c, muchie (x, y)));
	}
	fin.close();
	for (int i = 1; i <= n; ++i)
		tata[i] = i;
	sort (graf.begin(), graf.end());
	for (int i = 0; R.size() < n - 1 && i < m; ++i)
		if (find (graf[i].xx) != find (graf[i].yy)) {
			unite (find (graf[i].xx), find (graf[i].yy));
			sol += graf[i].c;
			R.push_back (graf[i].second);
		}
	ofstream fout (out); 
	fout << sol << "\n" << n - 1 << "\n";
	for (int i = 0; i < n - 1; ++i)
		fout << R[i].first << " " << R[i].second << "\n";
	fout.close();
	return 0;
}