#include "iostream"
#include "fstream"
#include "queue"
#include "vector"

using namespace std;

#define NMAX 200000

ifstream in("apm.in");
ofstream out("apm.out");

struct Graf {
	unsigned from;
	unsigned to;
	int cost;
};

struct Compare 
{
	bool operator() (const Graf &a, const Graf &b) const
	{	
		return a.cost >= b.cost;
		// if (a.cost >= b.cost && a.to != b.to) return true;
		// if (a.cost < b.cost && a.to != b.to) return false;
	}
};

vector < vector <Graf> > lista;
priority_queue <Graf, vector <Graf>, Compare> Q;
bool *checked;
int nr_nod;

void Read()
{
	int nr_muchii, x, y, cost;
	in >> nr_nod >> nr_muchii;

	checked = (bool*)calloc(nr_nod+1,sizeof(bool));
	for (int i = 0; i < nr_nod+1; i++) checked[i] = false;
		
	lista.resize(nr_nod+1);
	
	Graf pair ;
	
	for (int i = 0; i < nr_muchii; ++ i)
	{
		in >> x >> y >> cost;

		pair.from = x;
		pair.to = y;
		pair.cost = cost;
		lista[x].push_back(pair);

		pair.from = y;
		pair.to = x;
		pair.cost = cost;
		lista[y].push_back(pair);
	}
}

Graf Find_adjacent(int x)
{
	checked[x] = true;
	Graf pair;
	for (int i = 1; i < nr_nod+1; ++ i)
		if (checked[i])
			for (unsigned j = 0; j < lista[i].size(); ++ j)
				if ( !checked[ lista[i][j].to ] )
				{
					pair.from = i;
					pair.to = lista[i][j].to;
					pair.cost = lista[i][j].cost;
					Q.push(pair);
				}
	Graf c = Q.top();
	while (!Q.empty())	Q.pop();
	return c;
}

bool If_checked()
{
	for (int i = 1; i < nr_nod+1; ++i)
		if (!checked[i]) return false;
	return true;
}
void Prim(int &cost, int &nr_pair, vector <Graf> &result) 
{
	Graf c = Find_adjacent(1);
	while(!If_checked())
	{
		cost += c.cost;
		nr_pair ++;
		result.push_back(c);
		c = Find_adjacent(c.to);
	}
}
void Print(int cost, int nr_pair, vector <Graf> result)
{
	// for (int i = 1; i < nr_nod+1; ++ i)
	// {
	// 	cout << i << " | " ;
	// 	for (int j = 0; j < lista[i].size(); ++ j)
	// 		cout << lista[i][j].to << " ";
	// 	cout << "\n";
	// }
	out << cost << "\n" << nr_pair << "\n";
	for (unsigned i = 0; i < result.size(); ++i)
		out << result[i].from << " " << result[i].to << "\n";

}
int main(int argc, char const *argv[])
{
	Read();
	int cost = 0;
	int nr_pair = 0;
	vector <Graf> result;

	Prim(cost, nr_pair, result);
	Print(cost, nr_pair, result);	
	return 0;
}