#include<algorithm>
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

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

#define MAXEDGES 400000
#define MAXNODES 200000

int father[MAXNODES+1],depth[MAXNODES+1];
int num_nodes,num_edges;

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

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

int unite(int first_root,int second_root){
	if(depth[first_root]==depth[second_root]){
		father[first_root]=second_root;
		depth[second_root]++;
	}
	else if(depth[first_root]<depth[second_root]){
		father[first_root]=second_root;
	}
	else{
		father[second_root]=first_root;
	}
}

int get_root(int node){
	while(father[node]){
		node=father[node];
	}
	return node;
}

void solve(){
	sort(edges,edges+num_edges,compare);

	int cost=0;
	vector<edge>result;
	for(int i=0;i<num_edges;i++){
		edge e=edges[i];
		int roota=get_root(e.a),rootb=get_root(e.b);
		if(roota!=rootb){
			unite(roota,rootb);
			result.push_back(e);
			cost+=e.cost;
		}
	}
	out<<cost<<'\n'<<result.size()<<'\n';
	for(const edge&e:result)
		out<<e.a<<' '<<e.b<<'\n';
}

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;
	}
}


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

}