#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#define NMAX 200005
using namespace std;

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

int n, m, parinte[NMAX];
vector <pair <int, int> > G[NMAX];
priority_queue <pair <int, int> > pq;
bitset <NMAX> checked;

int main ()
{
	fin >> n >> m;
	int x, y, c;
	for (int i = 1; i <= m; ++i) {
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y,c));
		G[y].push_back(make_pair(x,c));
	}
	int node = 1, k = 1, nou, sum = 0;
	checked[1] = 1;
	while (k < n) {
		for (int i = 0; i < G[node].size(); ++i) {
			pair <int, int> per = make_pair(-G[node][i].second,G[node][i].first);
			pq.push(per);
		}
		while (checked[pq.top().second]) {
			pq.pop();
		}
		nou = pq.top().second;
		checked[nou] = 1;
		sum += -pq.top().first;
		pq.pop();
		parinte[nou] = node;
		node = nou;
		++k;
	}
	//cout << node;
	fout <<	sum << '\n';
	fout << n - 1 << '\n';
	while (node != 1) {
		fout << node << " " << parinte[node] << '\n';
		node = parinte[node];
	}
	
	fin.close();
	fout.close();
	return 0;
}