#include <fstream>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

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

set<pair<int,pair<int,int> > > graph;
vector<pair<int,int> > mstedges;
int dad[200100];
int vertices,edges,mstcost;

void read(){
	in>>vertices>>edges;
	int i,x,y,c;
	for(i=1;i<=edges;++i){
		in>>x>>y>>c;
		graph.insert(make_pair(c,make_pair(x,y)));
	}
}

int root(int x){
	int rt=x,xcopy=x;
	while(dad[x]){
		x=dad[x];
	}
	rt=x;
	x=xcopy;
	while(dad[x]){
		xcopy=x;
		x=dad[x];
		dad[xcopy]=rt;
	}
	return rt;
}

void Kruskal(){
	set<pair<int,pair<int,int> > >::iterator it;
	pair<int,pair<int,int> > currentedge;
	int node1,node2,cost;
	for(it=graph.begin();it!=graph.end();it++){
		currentedge=*it;
		node1=currentedge.second.first;
		node2=currentedge.second.second;
		cost=currentedge.first;
		if(root(node1)!=root(node2)){
			mstcost+=cost;
			mstedges.push_back(make_pair(node1,node2));
			dad[root(node1)]=node2;
		}
	}
	out<<mstcost<<"\n"<<vertices-1<<"\n";
	for(int i=0;i<mstedges.size();++i){
		out<<mstedges[i].first<<" "<<mstedges[i].second<<"\n";
	}
}

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