//Algoritmul lui Prim
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

#define in "apm.in"
#define out "apm.out"
#define N 5005
#define INF 1 << 30

struct muchie {
	int x, y;
};

muchie init (int x, int y)
{
	muchie a;
	a.x = x; a.y = y;
	return a;
}

vector <muchie> R;
vector <bool> d (N, 1);
vector <int> cmin (N), p (N);
int C[N][N], n, m, cost;

int main ()
{
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j)
			C[i][j] = C[j][i] = INF;
	for (int i = 0; i < m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		C[x][y] = C[y][x] = c;
	}
	fin.close();
	//Presupun nodul 1 ca fiind nod de start
	for (int i = 2; i <= n; ++i) {
		cmin[i] = C[1][i];
		p[i] = 1;
	}
	d[1] = 0;
	int sel = n - 1, vf;
	while (sel) {
		cost = INF;
		for (int i = 1; i <= n; ++i)
			if (d[i] && cost > cmin[i]) {
				cost = cmin[i];
				vf = i;
			}
		d[vf] = 0;
		--sel;
		for (int i = 1; i <= n; ++i)
			if (d[i] && C[i][vf] < cmin[i]) {
				p[i] = vf;
				cmin[i] = C[i][vf];
			}
	}
	ofstream fout (out);
	int tcost = 0;
	for (int i = 2; i <= n; ++i) {
		tcost += C[i][p[i]];
		R.push_back (init (p[i], i));
	}
	fout << tcost << "\n" << n - 1 << "\n";
	for (int i = 0; i < n - 1; ++i)
		fout << R[i].x << " " << R[i].y << "\n";
	fout.close();
	return 0;
}