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

struct muchie {
	int x,y,c;
};

muchie D[NMAX];
bool v[NMAX];
int p[200005];
int x,y,c,n,m;
int k,cost;

int find(int x) {
	if (p[x]==x) return x;
	int y=find(p[x]);
	p[x]=y;
	return y;
}

bool cmp(muchie l, muchie r) {
	return (l.c<r.c);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	cin>>n>>m;
	for (int i=1; i<=m; i++) {
		cin>>x>>y>>c;
		D[i] = {x,y,c};
	}	
	
	sort(D+1,D+m+1, cmp);
	for (int i=1; i<=n; i++) p[i]=i;
	
	for (int i=1; i<=m; i++) {
		int a=find(D[i].x), b=find(D[i].y);
		if (a!=b) {
			p[a]=p[b];
			cost+=D[i].c; k++; v[i]=1;
		}
	}
	
	cout<<cost<<'\n'<<k<<'\n';
	for (int i=1; i<=m; i++) 
		if (v[i]) cout<<D[i].x<<" "<<D[i].y<<'\n';
	
	
	
	
	return 0;
}