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

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

int n, m;
vector <pair<int, int> > g[NMAX], sol;
bitset <NMAX> checked;
struct Drum {
	int nod, tata, dist;
	Drum (int x, int y, int z) {
		nod = x;
		tata = y;
		dist = z;
	}
	bool operator<(const Drum& altu) const {
		return dist > altu.dist;
	}
};
priority_queue <Drum> pq;

int main ()
{
	fin >> n >> m;
	int x, y, z;
	for (int i = 1; i <= m; ++i) {
		fin >> x >> y >> z;
		g[x].push_back(make_pair(y,z));
		g[y].push_back(make_pair(x,z));
	}
	int s = 0;
	pq.push(Drum(1,0,0));
	while (pq.size()) {
		Drum d = pq.top();
		pq.pop();
		if (checked[d.nod]) {
			continue;
		}
		checked[d.nod] = 1;
		s += d.dist;
		sol.push_back(make_pair(d.tata,d.nod));
		for (int i = 0; i < g[d.nod].size(); ++i) {
			Drum nou = Drum(g[d.nod][i].first, d.nod, g[d.nod][i].second);
			if (!checked[nou.nod]) {
				pq.push(nou);
			}
		}
	}
	fout << s << '\n';
	fout << n-1 << '\n';
	for (int i = 1; i < sol.size(); ++i) {
		fout << sol[i].first << " " << sol[i].second << '\n';
	}
	
	fin.close();
	fout.close();
	return 0;
}