#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=200020;
struct muchie{
	int x,y,z;
}a[N];
vector <pair<int,int> > rs;
bool cmp(muchie b, muchie c){
	return(b.z<c.z);
}
int s[N], k[N];
int find(int x){
	int y=x;
	while(x!=k[x])x=k[x];
	while(y!=k[y]){
		int c=y;
		y=k[y];
		k[c]=x;
	}
	return x;
}
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(s[x]<s[y])swap(x,y);
	s[x]+=s[y];
	k[y]=k[x];
	find(y);
}
int main(){
	ifstream f("apm.in");
	ofstream g("apm.out");
	int n,m;
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>a[i].x>>a[i].y>>a[i].z;
	}
	sort(a+1,a+1+m,cmp);
	int sol=0;
	for(int i=1;i<=n;i++)s[i]=1, k[i]=i;
	for(int i=1;i<=m;i++)if(find(a[i].x)!=find(a[i].y)){
		unite(a[i].x, a[i].y);
		sol+=a[i].z;
		rs.pb({a[i].x, a[i].y});
	}
	g<<sol<<'\n'<<rs.size()<<'\n';
	for(int i=0;i<rs.size();i++)g<<rs[i].second<<' '<<rs[i].first<<'\n';
}