#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];
bitset <NMAX> checked;
struct Drum {
	int nod, tata, dist;
	Drum (int x, int y, int z) {
		tata = x;
		nod = y;
		dist = z;
	}
	bool operator<(const Drum& altu) const {
		return dist < altu.dist;
	}
};
priority_queue <Drum> pq;
vector <pair <int, int> > sol;

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 nod = 1, tata, sum = 0, k = 1;
	pq.push(Drum(0,1,0));
	while (pq.size()) {
		/*while (checked[pq.top().nod]) {
			pq.pop();
		}*/
		Drum dr = pq.top();
		tata = dr.tata;
		nod = dr.nod;
		int s = dr.dist;
		pq.pop();
		if (checked[nod]) {
			continue;
		}
		checked[nod] = 1;
		sum += -s;
		sol.push_back(make_pair(tata,nod));
		for (int i = 0; i < G[nod].size(); ++i) {
			Drum per = Drum(nod,G[nod][i].first,-G[nod][i].second);
			//per.nod = G[node][i].first;
			//per.tata = node;
			//per.dist = -G[node][i].second;
			if (!checked[per.nod]) {	
				pq.push(per);
			}
		}
		//cout << tata << " " << nod << endl;
	}
	//cout << node;
	fout <<	sum << '\n';
	fout << n - 1 << '\n';
	/*while (node != 1) {
		fout << node << " " << parinte[node] << '\n';
		node = parinte[node];
	}*/
	for (int i = 1; i < sol.size(); ++i) {
		fout << sol[i].first << " " << sol[i].second << '\n';
	}
	
	fin.close();
	fout.close();
	return 0;
}