#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

#define NMax 200010
#define MMax 400010

struct muchie{
	int x, y;
	int c;
	bool operator()(muchie & ob1, muchie & ob2){
		return ob1.c < ob2.c;
	}
};

int n, m;
muchie G[MMax];

vector<int> apm;
int cost;

// union-find
int tata[NMax];
int Find(int);
void Union(int, int);
// end

void init();
void rezolvare();
void afisare();

int main(){
	init();
	rezolvare();
	afisare();
}

void init(){
	int i, x, y, c;
	fin >> n >> m;
	for(i = 0; i < m; i++)
		fin >> G[i].x >> G[i].y >> G[i].c;
	apm.reserve(m);
}

void rezolvare(){
	int i, j;
	sort(G, G + m, muchie());
	for(i = 0; i < m; i++)
		if(Find(G[i].x) != Find(G[i].y)){
			Union(Find(G[i].x), Find(G[i].y));
			apm.push_back(i);
			cost += G[i].c;
		}
}

void afisare(){
	int i;
	fout << cost << '\n' << n - 1 << '\n';
	for(i = 0; i < n - 1; i++) fout << G[apm[i]].x << ' ' << G[apm[i]].y << '\n';
}

int Find(int x){
	int y, r = x;
	while(tata[r]) r = tata[r];
	while(tata[x]){
		y = x;
		x = tata[x];
		tata[y] = r;
	}
	return r;
}

void Union(int x, int y){
	tata[x] = y;
}