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

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

int n,m;
vector<int> father; // father[i] - the father of the node i
vector<int> depth;  // depth[i] - the depth of the tree rooted at i

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

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

struct edge{
	int a,b,cost;
};

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

void read(){
	in>>n>>m;

	edges.resize(m);
	father.resize(n+1);
	depth.resize(n+1);

	for(int i=0;i<m;i++){
		in>>edges[i].a>>edges[i].b>>edges[i].cost;
	}
}

void solve(){
	sort(edges.begin(),edges.end(),compare);
	int cost=0;
	vector<edge> result;

	for(const edge&e:edges){
		int first=root(e.a),second=root(e.b);
		if(first!=second){
			cost+=e.cost;
			merge(first,second);
			result.push_back(e);
		}
	}
	out<<cost<<'\n';
	out<<result.size()<<'\n';
	for(edge k:result){
		out<<k.a<<" "<<k.b<<'\n';
	}
}

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