#include <bits/stdc++.h>

using namespace std;

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

vector<int> p;
vector<tuple<int,int,int>> edge, apm;
int n, m, sum;
int c, u, v;

inline int parent(int a){
	return p[a]<0 ? a : p[a]=parent(p[a]);
}

void unite(int a, int b){
	a=parent(a);
	b=parent(b);
	if(a==b)
		return;
	if(p[a]>p[b])
		swap(a,b);

	p[a]+=p[b];
	p[b]=a;
}

int main(){
	f>>n>>m;
	p.resize(n+1,-1);
	for(int i=1;i<=m;i++){
		f>>u>>v>>c;
		edge.push_back(make_tuple(c, u, v));
	}
	sort(edge.rbegin(),edge.rend());
	while(!edge.empty()){
		tie(c, u, v)=edge.back();
		if(parent(u) != parent(v)){
			apm.push_back(make_tuple(u, v, 0));
			unite(u,v);
			sum+=c;
		}
		edge.pop_back();
	}
	g<<sum<<'\n';
	g<<apm.size()<<'\n';
	for(auto it: apm){
		tie(u,v,c)=it;
		g<<u<<' '<<v<<'\n';
	}
	return 0;
}