#include<bits/stdc++.h>
using namespace std;


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

int num_nodes,num_edges;


struct edge{
	int a,b,cost;
} edges[400000];

bool cmp(edge&a,edge&b){
	return a.cost<b.cost;
}


int father[200001];
int depth[200001];

int root(int a){
	while(father[a])
		a=father[a];

	return a;
}

void read(){
	in>>num_nodes>>num_edges;
	for(int i=0;i<num_edges;i++)
		in>>edges[i].a>>edges[i].b>>edges[i].cost;
	sort(edges,edges+num_edges,cmp);
}

void unite(int a,int b){
	if(depth[a]==depth[b]){
		father[b]=a;
		depth[a]++;
	}
	else if(depth[a]<depth[b]){
		father[a]=b;
	}
	else{
		father[b]=a;
	}
}




void kruskal(){
	int cost=0;
	vector<std::pair<int,int>> results;
	for(int i=0;i<num_edges;i++){
		int a=edges[i].a;
		int b=edges[i].b;

		if(root(a)!=root(b)){
			unite(root(a),root(b));
			cost+=edges[i].cost;
			results.push_back({a,b});
		}
	}

	out<<cost<<'\n';
	out<<results.size()<<'\n';
	for(int i=0;i<results.size();i++)
		out<<results[i].first<<" "<<results[i].second<<'\n';

}


int main(){
	read();
	kruskal();

	return 0;
}