#include <fstream>
#include <queue>

using namespace std;

typedef struct elem
{
	int rank;
	struct elem* parent;
}Elem;

typedef struct edge
{
	int x, y, c;
public:
	edge(int x, int y, int c) : x(x), y(y), c(c) {};
}Edge;

Elem** CreateSets(int n);
Elem* Find(Elem* x);
void Union(Elem* x, Elem* y);

int main()
{
    ifstream fin;
    ofstream fout;
    fout.open("apm.out");
    fin.open("apm.in");

    int n, m, x, y, c;
    fin >> n >> m;

    Elem** elemList = CreateSets(n);

    auto cmp = [](Edge* left, Edge* right) { return left->c > right->c; };
    priority_queue<int, std::vector<Edge*>, decltype(cmp)> queue(cmp);

    for(int i = 1; i <= m; i++)
    {
    	fin >> x >> y >> c;
    	queue.push(new Edge(x,y,c));
    }

    int cost = 0;
    int nr = 0;
    vector<Edge*> solution;

    while(!queue.empty())
    {
    	Edge* edge = queue.top();
    	queue.pop();

    	if(Find(elemList[edge->x]) != Find(elemList[edge->y]))
    	{
    		Union(elemList[edge->x], elemList[edge->y]);
    		cost += edge->c;
    		nr++;
    		solution.push_back(edge);
    	}
    }

    fout << cost << "\n";
    fout << nr << "\n";
    for(vector<Edge*>::iterator it = solution.begin(); it != solution.end(); ++it)
    	fout << (*it)->x << " " <<(*it)->y << "\n";

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

Elem** CreateSets(int n)
{
	Elem** list = new Elem*[n + 1]();

	for(int i = 1; i <= n; i++)
	{
		list[i] = new Elem();
		list[i]->rank = 0;
		list[i]->parent = list[i];
	}

	return list;
}

Elem* Find(Elem* x)
{
	if(x->parent != x)
		x->parent = Find(x->parent);

	return x->parent;
}

void Union(Elem* x, Elem* y)
{
    Elem* xRoot = Find(x);
    Elem* yRoot = Find(y);

    if(xRoot == yRoot)
        return;

    if(xRoot->rank > yRoot->rank)
        yRoot->parent = xRoot;
    else if(yRoot->rank > xRoot->rank)
        xRoot->parent = yRoot;
    else
    {
        yRoot->parent = xRoot;
        xRoot->rank += 1;
    }
}