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

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); }
	pq muchii(cmp, v);

	merge_find mf(n);
	int suma = 0, nr = 0, x, y, c, X, Y;
	vector<pair<int, int> > rez;
	while(!mf.unit()){
		tie(x, y, c) = muchii.top();
		muchii.pop();
		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; }