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

using namespace std; 

std::ifstream f("apm.in");
std::ofstream g("apm.out");

int N, M, mstCost;

class Edge{
public:
	int start,end,cost;
	Edge(int s,int e , int c){
		start = s;
		end = e;
		cost = c;
	}
};

vector<Edge> edges;
vector<Edge> MST;

/*deal with sets*/
int parent[200001];
int rankLvl[200001];
int find(int x){
	if(parent[x] != x){
		parent[x] = find(parent[x]);
	}
	return parent[x];
}

void Union(int x,int y){
	int xRoot = find(x);
	int yRoot = find(y);
	if(xRoot == yRoot){
		return;
	}
	//
	
	if(rankLvl[xRoot] < rankLvl[yRoot]){
		parent[xRoot] = yRoot;
	}else if(rankLvl[xRoot] > rankLvl[yRoot]){
		parent[yRoot] = xRoot;
	}else{
		parent[yRoot] = xRoot;
		rankLvl[xRoot] += 1;
	}
}

class Cmp{
public:
   bool operator() ( const Edge & p1, const Edge & p2 ) const
   {
     return p1.cost < p2.cost;
   }
};

void read(){
	f >> N >> M;
	int start,end,cost;

	for(int i = 1 ; i <= N ; ++i){
		parent[i] = i;
	}

	for(int i = 0 ; i < M ; ++i){
		f >> start >> end >> cost;
		edges.push_back(Edge(start,end,cost));
	}
	sort(edges.begin(), edges.end(), Cmp());
}

void Kruskal(){
	int size = N - 1;
	int pos = 0;
	int start,end,cost;


	while(MST.size() != size){
		start = edges.at(pos).start;
		end = edges.at(pos).end;
		cost = edges.at(pos).cost;
		
		if(find(start) != find(end)){
			Union(start,end);
			mstCost += cost;
			MST.push_back(edges.at(pos));
		}
		++pos;
	}

}



int main(){
	read();
	Kruskal();
	g << mstCost << "\n";
	g << N - 1 << "\n";
	for(int i = 0 ; i < MST.size(); ++i){
		g << MST.at(i).start <<" " << MST.at(i).end <<"\n";
	}

	
	return 0 ;
}