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

using namespace std;

struct node
{
	int left, right, value;
	node() {};
	node(const int &i, const int &j, const int &v)
	{
		left=i;
		right=j;
		value=v;
	}
}__attribute__((__packed__));

struct cmp
{
	bool operator()(const node &left, const node &right) const
	{
		if (left.value < right.value)
			return 1;
		return 0;
	}
};

int nodes, edges;
node V[400001];
int tata[200001];

int father(int i)
{
	stack<int > S;
	int father=i;
	while (tata[father] != 0)
	{
		S.push(father);
		father=tata[father];
	};
	while (!S.empty())
	{
		tata[S.top()]=father;
		S.pop();
	}
	return father;
}

vector<pair<int, int > > AFIS;

void solve(const char *buff_file, const char *out_file)
{
	fstream f(buff_file, ios::in);
	f>>nodes>>edges;
	int left, right, value;
	for (int i=1; i<=edges; ++i)
	{
		f>>left>>right>>value;
		V[i]=node(left, right, value);
	}
	sort(V+1, V+edges+1, cmp());
	
	int out_val=0;
	int out_nr=0;
	AFIS.reserve(nodes+1);
	int tata_left, tata_right;
	
	for (int i=1; i<=edges && ((out_nr+1)<nodes); ++i)
	{
		tata_left=father(V[i].left);
		tata_right=father(V[i].right);
		if ( (tata_left != tata_right) || (tata_left==tata_right && tata_left==0))
		{
			++out_nr;
			out_val+=V[i].value;
			tata[tata_left]=tata_right;
			AFIS.push_back(make_pair(V[i].left, V[i].right));
		}
	}
	
	fstream g(out_file, ios::out);
	g<<out_val<<"\n"<<AFIS.size()<<"\n";
	for (vector<pair<int, int> >::iterator it=AFIS.begin(); it < AFIS.end(); it++)
		g<<it->first<<" "<<it->second<<"\n";
	g.close();
	
};

int main()
{
	solve("apm.in", "apm.out");
	return 0;
}