#include <cstdio>
#include <algorithm>
#define N 200001
#define M 400001
using namespace std;
int n, m, t[N], nr;
long long s;
struct nod{
	int x, y, cost;
} v[M];
struct nod1{
	int x, y;
} sol[N];
struct cmp{
	bool operator()(const nod &a, const nod &b)const{
		if(a.cost < b.cost)
			return true;
		return false;
	}
};
int findRoot(int i){
	if(i != t[i])
		t[i] = findRoot(t[i]);
	return t[i];
}
int ok(int x, int y){
	int X = findRoot(x), Y = findRoot(y);
	if(X == Y)
		return false;
	return true;
}
void solve(int x, int y, int c){
	if(ok(x, y)){
		int X = findRoot(x), Y = findRoot(y);
		t[X] = Y;
		sol[++nr].x = x;
		sol[nr].y = y;
		s += c;
	}
}
int main(){
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d ", &n, &m);
	for(int i = 1; i <= n; ++i)
		t[i] = i;
	for(int i = 1; i <= m; ++i)
		scanf("%d %d %d ", &v[i].x, &v[i].y, &v[i].cost);
	sort(v + 1, v + m + 1, cmp());
	for(int i = 1; i <= m; ++i)
		solve(v[i].x, v[i].y, v[i].cost);
	printf("%lld\n%d\n", s, nr);
	for(int i = 1; i <= nr; ++i)
		printf("%d %d\n", sol[i].x, sol[i].y);
}