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

#define RANGE_MIN -1000
#define RANGE_MAX 1000

using namespace std;

template<typename BidIt, typename RanIt, typename IntRanIt, class Functor>
void counting_sort_copy_with_counters(
    BidIt begin_to_sort, BidIt end_to_sort,
    RanIt sorted, IntRanIt counters,
    size_t n_keys, Functor get_key)
{
    std::fill_n(counters, n_keys, 0);
    for (BidIt it = begin_to_sort; it != end_to_sort; ++it) {
        ++counters[get_key(*it)];
    }
    for (IntRanIt it = counters + 1; it != counters + n_keys; ++it) {
        *it += *(it - 1);
    }
    for (BidIt it = end_to_sort; it != begin_to_sort; ) {
        sorted[--counters[get_key(*--it)]] = *it;
    }
}


template<typename BidIt, typename RanIt, class Functor>
void counting_sort_copy(
    BidIt begin_to_sort, BidIt end_to_sort,
    RanIt sorted,
    size_t n_keys, Functor get_key)
{
    std::vector<int> counters(n_keys);
    counting_sort_copy_with_counters(begin_to_sort, end_to_sort, sorted,
        counters.begin(), n_keys, get_key);
}


template<typename BidIt, class Functor>
void counting_sort(BidIt begin_to_sort, BidIt end_to_sort, size_t n_keys, Functor get_key){
    vector<typename iterator_traits<BidIt>::value_type> sorted(distance(begin_to_sort, end_to_sort));
    counting_sort_copy(begin_to_sort, end_to_sort, sorted.begin(), n_keys, get_key);
    copy(sorted.begin(), sorted.end(), begin_to_sort);
}

struct nodp{
	int r;
	nodp *p;
};

struct muchie{
	int c1, c2, cost;
	bool sel;
};

int muchie_gk(muchie const & a){
	return a.cost-RANGE_MIN;
}

void cset(nodp * x){
	x->p=x;
	x->r=0;
}

nodp * gaseste(nodp * x){
	if(x->p==x)
		return x->p;
	return gaseste(x->p);
}

inline void uneste(nodp * x, nodp * y){
	nodp * xRoot=gaseste(x);
	nodp * yRoot=gaseste(y);
	if(xRoot==yRoot)
		return;
	if(xRoot->r < yRoot->r)
		xRoot->p=yRoot;
	else if(xRoot->r > yRoot->r)
		yRoot->p=xRoot;
	else{
		yRoot->p=xRoot;
		xRoot->r++;
	}
}

int main(){
	int n, m, i, sum=0, msel=0;
	muchie *M;
	{//citire
		ifstream fp("apm.in");
		fp>>n>>m;
		M=new muchie[m];
		for(i=0; i<m; i++){
			fp>>M[i].c1>>M[i].c2>>M[i].cost;
			M[i].sel=0;
		}
		fp.close();
	}
	{//Kruskal
		nodp *N;
		N=new nodp[n+1];
		for(i=1; i<=n; i++)
			cset(&N[i]);
		counting_sort(M, M+m, RANGE_MAX-RANGE_MIN+1, muchie_gk);
		for(i=0; i<m; i++)
			if(gaseste(&N[M[i].c1]) != gaseste(&N[M[i].c2])){
				M[i].sel=1;
				sum+=M[i].cost;
				msel++;
				if(msel==n-1)
					break;
				uneste(&N[M[i].c1], &N[M[i].c2]);
			}
	}
	{//afisare
		ofstream fp("apm.out");
		fp<<sum<<endl<<msel<<endl;
		for(i=0; i<m; i++)
			if(M[i].sel)
				fp<<M[i].c1<<" "<<M[i].c2<<endl;
	}
	return 0;
}