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

using namespace std;

struct muchie
{
	int nod1;
	int nod2;
	int cost;
};

vector<muchie> graph;
vector <pair <int, int> > graph_final;
int n, m, costTotal;

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

class DisjointDataSet 
{
	vector<int> rang;
	vector<int> parent;
public:
	DisjointDataSet(int);
	int findRoot(int);
	void link(int, int);
	void unionSets(int, int);
};

DisjointDataSet::DisjointDataSet(int n)
{
	rang.resize(n + 1, 0);
	parent.resize(n + 1);
	for (int i = 0; i < n + 1; i++)
		parent[i] = i;
}


int DisjointDataSet::findRoot(int x) 
{
	int i, aux;

	for (i = x; parent[i] != i; i = parent[i])
	{

	}
	while (parent[x] != x) 
	{
		aux = parent[x];
		parent[x] = i;
		x = aux;
		rang[i]--;
	}
	return i;
}

void DisjointDataSet::link(int x, int y) 
{
	if (rang[x] < rang[y]) 
		parent[x] = y;
	else
	{
		if (rang[x] > rang[y])
			parent[y] = x;
		else 
		{
			parent[x] = y;
			rang[y]++;
		}
	}
}

void DisjointDataSet::unionSets(int x, int y)
{
	link(findRoot(x), findRoot(y));
}

bool cmp(const muchie &a, const muchie &b)
{
	if (a.cost < b.cost)
		return true;
	return false;
}

void kruskal()
{
	sort(graph.begin(), graph.end(), cmp);
	DisjointDataSet d(n);
	int x, y, c;
	for (int i = 0; i < graph.size(); i++)
	{
		x = graph[i].nod1;
		y = graph[i].nod2;
		c = graph[i].cost;
		if (d.findRoot(x) != d.findRoot(y)) 
		{
			graph_final.push_back(make_pair(x, y));
			d.unionSets(x, y);
			costTotal += c;
		}
	}
}

int main() 
{
	f >> n >> m;
	for (int i = 0; i < m; i++)
	{
		muchie mch;
		f >> mch.nod1 >> mch.nod2 >> mch.cost;
		graph.push_back(mch);
	}
	kruskal();
	g << costTotal << endl<< graph_final.size() << endl;
	for (auto it = graph_final.begin(); it != graph_final.end(); it++) 
	{
		g << it->first << " " << it->second << endl;
	}
	f.close();
	g.close();
	return 0;
}