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

using namespace std;

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

bool vi[200041];
struct muc{
	int a, b, v;
	bool operator<(const muc &rhs)const{
		return v > rhs.v;
	}
	int fal()const{
		if(vi[a]){
			return b;
		}else{
			return a;
		}
	}
	bool don(){
		return vi[a]&&vi[b];
	}
};

int n, m;
priority_queue<muc> pq;
vector<int> gra[200041];

muc muci[400041];

vector<muc> sol;

void hitme(int a){
	auto &x = gra[a];
	vi[a] = 1;
	for(int i = 0; i < x.size(); ++i){
		muc y = muci[x[i]];
		if(!y.don()){
			pq.push(y);
		}
	}
}

muc nextto(){
	muc x;
	do{
		x = pq.top();
		pq.pop();
	}while(x.don() && !pq.empty());
	return x;
}

int mentos(){
	int s = 0;
	for(auto x : sol){
		s += x.v;
	}
	return s;
}

int main(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		muc &x = muci[i];
		fin >> x.a >> x.b >> x.v;
		gra[x.a].push_back(i);
		gra[x.b].push_back(i);
	}
	
	hitme(1);
	for(int i = 2; i <= n; ++i){
		muc x = nextto();
		sol.push_back(x);
		hitme(x.fal());
	}
	
	fout << mentos() << "\n";
	fout << sol.size() << "\n";
	for(auto x : sol){
		fout << x.a << " " << x.b << "\n";
	}
	return 0;
}