//#include "minspantree.h"

#ifndef _ALGORITHM_H
#define _ALGORITHM_H
#include <fstream>
using namespace std;

/**
	Algorithm abstract class
	specifies protocol
*/
template<class I, class O>
class Algorithm
{
protected:

	I &in;
	O &out;

	/**
		algorithm method
		instantiates i/o
	*/
	Algorithm(I &, O &);
};

/**
	algorithm method
	instantiates i/o
*/
template<class I, class O>
Algorithm<I, O>::Algorithm(I &inp, O &outp): in(inp), out(outp)
{

}

#endif

#ifndef _UNIONFIND_H
#define _UNIONFIND_H

#include <vector>
using namespace std;

/**
	UnionFind class
	solves the disjoint sets union find problem
*/
class UnionFind: public Algorithm< int, bool >
{
	int N;
	vector<int> Ftr;

public:

	/**
		unionfind method
		runs algorithm
	*/
	UnionFind(int &, bool &);

	/**
		union method
		reunites two sets
	*/
	void Union(int, int);

	/**
		find method
		finds set
	*/
	int Find(int);

	/**
		update method
		updates set
	*/
	void Update(int, int);
};

#endif

/**
	unionfind method
	runs algorithm
*/
UnionFind::UnionFind(int &in, bool &out): 
	Algorithm<int, bool>(in, out), N(0)
{
	N = in;
	Ftr.assign(N + 1, -1);
}

/**
	union method
	reunites two sets
*/
void UnionFind::Union(int x, int y)
{
	int i, j, c;

	i = Find(x);
	j = Find(y);

	if (Ftr[i] > Ftr[j])
	{
		Ftr[i] = j;
		c = j;
	}
	else if (Ftr[i] < Ftr[j])
	{
		Ftr[j] = i;
		c = i;
	}
	else
	{
		Ftr[i] = j;
		--Ftr[j];
		c = j;
	}

	Update(x, c);
	Update(y, c);
}

/**
	find method
	finds set
*/
int UnionFind::Find(int x)
{
	int i;

	for (i = x; Ftr[i] > 0; i = Ftr[i]); 
	
	Update(x, i);
	return i;
}

/**
	update method
	updates set
*/
void UnionFind::Update(int x, int c)
{
	int i;

	for (i = x; Ftr[i] > 0; i = x)
	{
		x = Ftr[i];
		Ftr[i] = c;
	}
}

#ifndef _MINSPANTREE_H
#define _MINSPANTREE_H

#include <vector>
#include <algorithm>
using namespace std;

/**
	MinSpanTreeEdge struct
	retains edges
*/
struct MinSpanTreeEdge
{
	int x, y, c;

	/**
		() operator
		used for comparing
	*/
	bool operator()(MinSpanTreeEdge, MinSpanTreeEdge);
};

/**
	MinSpanTree class
	solves the maximum flow in a network problem
*/
class MinSpanTree: public Algorithm< vector<int>, vector< pair<int, int> > >
{
	int N, M, A;
	vector<MinSpanTreeEdge> Edg, Ans;

public:

	/**
		minspantree method
		runs algorithm
	*/
	MinSpanTree(vector<int> &, vector< pair<int, int> > &);

private:

	/**
		read method
		reads input
	*/
	void Read();

	/**
		solve method
		solves problem
	*/
	void Solve();

	/**
		write method
		writes output
	*/
	void Write();
};

#endif

/**
	minspantree method
	runs algorithm
*/
MinSpanTree::MinSpanTree(vector<int> &in, vector< pair<int, int> > &out): 
	Algorithm< vector<int>, vector< pair<int, int> > >(in, out), A(0)
{
	Read();
	Solve();
	Write();
}

/**
	read method
	reads input
*/
void MinSpanTree::Read()
{
	int f;
	MinSpanTreeEdge e;

	N = in[0];
	M = in[1];

	for (f = 0; f < M; ++f)
	{
		e.x = in[f * 3 + 2];
		e.y = in[f * 3 + 3];
		e.c = in[f * 3 + 4];
		Edg.push_back(e);
	}
}

/**
	compare method
	compares two edges output
*/
bool MinSpanTreeEdge::operator()(MinSpanTreeEdge edge1, MinSpanTreeEdge edge2)
{
	return edge1.c < edge2.c;
}

/**
	solve method
	solves problem
*/
void MinSpanTree::Solve()
{
	vector<MinSpanTreeEdge>::iterator i;
	MinSpanTreeEdge e;
	int j;

	e.x = e.y = e.c = 0;
	sort(Edg.begin(), Edg.end(), e);

	bool K = true;

	UnionFind uf(N, K);

	for (i = Edg.begin(), j = 1; i != Edg.end() && j < N; ++i)
	{
		if (uf.Find(i->x) != uf.Find(i->y))
		{
			A += i->c;
			uf.Union(i->x, i->y);
			Ans.push_back(*i);
			++j;
		}
	}
}

/**
	write method
	writes output
*/
void MinSpanTree::Write()
{
	vector<MinSpanTreeEdge>::iterator i;

	out.push_back(pair<int, int>(A, Ans.size()));

	for (i = Ans.begin(); i != Ans.end(); ++i)
	{
		out.push_back(pair<int, int>(i->x, i->y));
	}
}



int main()
{
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	int N, M, x, y, c;

	vector<int> I;
	vector< pair<int, int> > O;

	fin >> N >> M;
	I.push_back(N);
	I.push_back(M);

	while (M--)
	{
		fin >> x >> y >> c;
		I.push_back(x);
		I.push_back(y);
		I.push_back(c);
	}

	MinSpanTree mflow(I, O);

	fout << O[0].first << '\n' << O[0].second << '\n';

	for (unsigned c = 1; c < O.size(); ++c)
	{
		fout << O[c].first << ' ' << O[c].second << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}