#include <fstream>
#include <vector>
#include <queue>
#define mp make_pair
#define muchie pair<int, pair<int, int> >

using namespace std;

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


int n,m;
bool viz[200100];
vector <muchie> muchii[200100];
vector <muchie> results;
priority_queue< muchie,vector<muchie>,greater<muchie> > coada;

void read(){
	int x,y,c;
	in>>n>>m;
	for(int i=1;i<=m;++i){
		in>>x>>y>>c;
		muchii[x].push_back(mp(c,mp(x,y)));
		muchii[y].push_back(mp(c,mp(x,y)));
	}
}

void solve(){
	int nrmuchii=0,cost=0,vizitate=1,i;
	muchie aux;
	viz[1]=true;
	for(i=0;i<muchii[1].size();++i){
		coada.push(muchii[1][i]);
	}
	while(vizitate!=n){
		aux=coada.top();
		coada.pop();
		if(viz[aux.second.first]==1&& viz[aux.second.second]==0){
			cost+=aux.first;
			viz[aux.second.second]=1;
			nrmuchii++;
			vizitate++;
			results.push_back(aux);
			for(i=0;i<muchii[aux.second.second].size();++i){
				coada.push(muchii[aux.second.second][i]);
			}
		}
		if(viz[aux.second.second]==1&& viz[aux.second.first]==0){
			cost+=aux.first;
			viz[aux.second.first]=1;
			nrmuchii++;
			vizitate++;
			results.push_back(aux);
			for(i=0;i<muchii[aux.second.first].size();++i){
				coada.push(muchii[aux.second.first][i]);
			}
		}
	}
	out<<cost<<"\n"<<results.size()<<"\n";
	for(i=0;i<results.size();++i){
		out<<results[i].second.first<<" "<<results[i].second.second<<"\n";
	}
}

int main(){
	read();
	solve();
	return 0;
}