//#include "pch.h"
#include <iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;

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

vector<int> tata, rang;
priority_queue<pair<int, pair<int, int>>> pq;
vector< pair<int, pair<int, int>>> graph;
int s;
int father(int x, vector<int> &tata) {
	if (x == tata[x])
		return x;
	else {
		int dad = father(tata[x], tata);
		tata[x] = dad;
		return dad;
	}
}
bool is_conex(int x, int y, vector<int> &tata) {
	if (father(x, tata) == father(y, tata))
		return true;
	else
		return false;
}
void unire(int x, int y, vector<int> &tata, vector<int> &rang) {
	int tx = father(x, tata);
	int ty = father(y, tata);
	if (rang[x] < rang[y]) {
		tata[tx] = ty;
		rang[tx] += rang[ty];
	}
	else {
		tata[ty] = tx;
		rang[ty] += rang[tx];
	}
}
int main()
{
	int N, M;
	in >> N >> M;
	tata.resize(N + 1);
	rang.resize(N + 1, 1);
	for (int i = 1; i <= N; i++)
		tata[i] = i;
	for (int i = 0; i < M; i++) {
		int x, y, c;
		in >> x >> y >> c;
		pair<int, pair<int, int>> muchie=make_pair(-c,make_pair(x,y));
		pq.push(muchie);
	}

	while (!pq.empty()) {
		pair<int, pair<int, int>> muchie;
		muchie=pq.top();
		pq.pop();
		int c = muchie.first;
		int x = muchie.second.first;
		int y = muchie.second.second;
		if (is_conex(x, y, tata) == false) {
			unire(x, y, tata, rang);
			graph.push_back(make_pair(-c, make_pair(x, y)));
			s += -c;
		}
	}
	out << s << '\n'<< graph.size()<<'\n';
	for (int i = 0; i < graph.size(); i++)
		out << graph[i].second.first << ' ' << graph[i].second.second<<'\n';
	in.close();
	out.close();
	return 0;
}