#include <iostream>
#include <fstream>
#include <vector>

#define MAXN 200020

using namespace std;

int N,M;

struct Edge {
	int x,y,cost;
};

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

vector<Edge> E;
vector<Edge> APM;
int vis[MAXN],cost;

bool compare(Edge a,Edge b) {
	return a.cost < b.cost;
}

int read() {	
	int i;
	fin >> N >> M;
	E.resize(M);
	for (i=0;i<M;++i) {
		fin >> E[i].x >> E[i].y >> E[i].cost;
	}
	sort(E.begin(),E.end(),compare);
}

int solve() {
	int i,k;
	cost = 0;
	APM.push_back(E[0]);
	vis[E[0].x] = vis[E[0].y] = 1;
	cost += APM[0].cost;
	for (k=0;k<N-2;++k) {
		i = 1;
		while (vis[E[i].x] == vis[E[i].y]) ++i;
		APM.push_back(E[i]);
		vis[E[i].x] = vis[E[i].y] = 1;
		cost += E[i].cost;
	}
}

int write() {
	int i;
	fout << cost << "\n";
	fout << APM.size() << endl;
	for (i=0;i<APM.size();++i)
		fout << APM[i].x << " " << APM[i].y << "\n";
}

int main() {

	read();
	solve();
	write();
	
	fin.close();
	fout.close();
	
	return 0;
}