#include <fstream>
#include <vector>
#include <queue>
#include <numeric>
#include <tuple>
#include <utility>
#include <algorithm>
using namespace std;

template <typename It, typename F>
void radix_sort(It s, It d, F f){
	queue<typename It::value_type> val[256];
	for(int adanc = 0; adanc < 32; adanc+=8){
		for(It x = s; x != d; ++x){
			val[(f(*x)>>adanc)&0xff].push(*x); }
		It x = s;
		for(int i = 0; i < 256; ++i){
			while(!val[i].empty()){
				*x++ = val[i].front();
				val[i].pop(); } } }
	auto it = partition_point(s, d, [&f](const typename It::value_type& m){
		return f(m) > 0; });
	rotate(s, it, d); }

class merge_find{
	vector<int> parinti, adanc;
	int nr_arbori;
public:
	merge_find(const int n):
		parinti(n),
		adanc(n, 1),
		nr_arbori(n){
		iota(begin(parinti), end(parinti), 0); }
	bool unit(){
		return nr_arbori == 1; }
	int find(int a){
		static vector<int> vizitate;
		vizitate.clear();
		while(parinti[a] != a){
			vizitate.push_back(a);
			a = parinti[a]; }
		for(const auto x : vizitate){
			parinti[x] = a; }
		return a; }
	void merge(int a, int b){
		--nr_arbori;
		if(adanc[a] > adanc[b]){
			parinti[b] = a; }
		else if(adanc[a] < adanc[b]){
			parinti[a] = b; }
		else{
			parinti[a] = b;
			++adanc[b]; } } };

using muchie = tuple<int, int, int>;
auto cmp = [](const muchie& lhs, const muchie& rhs){
	return get<2>(lhs) > get<2>(rhs); };
using pq = priority_queue<muchie, vector<muchie>, decltype(cmp)>;


int main(){
	ifstream f("apm.in");
	int n, m;
	f >> n >> m;
	vector<muchie> v(m);
	for(auto& x : v){
		f >> get<0>(x) >> get<1>(x) >> get<2>(x);
		--get<0>(x), --get<1>(x); }
	radix_sort(begin(v), end(v), [](const muchie& m){return get<2>(m); });

	merge_find mf(n);
	auto it = begin(v);
	int suma = 0, nr = 0, x, y, c, X, Y;
	vector<pair<int, int> > rez;
	while(!mf.unit()){
		tie(x, y, c) = *it++;
		X = mf.find(x), Y = mf.find(y);
		if(X != Y){
			mf.merge(X, Y);
			suma += c;
			++nr;
			rez.emplace_back(x, y); } }
	ofstream g("apm.out");
	g << suma << '\n' << nr << '\n';
	for(const auto& p : rez){
		g << p.first+1 << ' ' << p.second+1 << '\n'; }
	return 0; }