#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

#define NMAX 200005
int rank[NMAX], P[NMAX];

int N, M;

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

typedef struct muchie muchie;

bool mycomparator(muchie m1, muchie m2){
	return m1.w < m2.w;
}

vector<muchie> muchii;

void citire(){
	FILE * f = fopen("apm.in", "rt");
	fscanf(f, "%d %d", &N, &M);
	for(int i = 0; i < M; ++i){
		muchie m;
		fscanf(f, "%d %d %d", &m.x, &m.y, &m.w);
		muchii.push_back(m);
	}
	fclose(f);
}

void make_set(int N){
	for(int i = 1; i <= N; ++i)
		P[i] = i, rank[i] = 1;
}

int parent(int u){
	if(u != P[u])
		P[u] = parent(P[u]);
	return P[u];
}

void link(int u, int v){
	if(rank[u] > rank[v])
		P[v] = u;
	else{
		P[u] = v;
		if(rank[u] == rank[v])
			++rank[v];
	}
}

void union_op(int u, int v){
	link(parent(u), parent(v));
}

int main(){
	citire();
	make_set(N);
	sort(muchii.begin(), muchii.end(), mycomparator);
	int sum = 0;
	vector<int> sol;
	for(unsigned i = 0; i < muchii.size(); ++i)
		if(parent(muchii[i].x) != parent(muchii[i].y)){
			sum += muchii[i].w;
			sol.push_back(i);
			union_op(muchii[i].x, muchii[i].y);
		}
	FILE * f = fopen("apm.out", "wt");
	fprintf(f, "%d\n%d\n", sum, sol.size());
	for(int i = 0; i < sol.size(); ++i)
		fprintf(f, "%d %d\n", muchii[sol[i]].x, muchii[sol[i]].y);
	fclose(f);

	return 0;
}