// Lab3.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

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

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

int n, m;
std::vector<std::vector<int>> G, Arb;
std::vector<int> cc;

void citire()
{
	int x, y, cost;
	in >> n >> m;
	while (in >> x >> y >> cost)
	{
		G.push_back({ cost,x,y });
	}
} 

void uneste(int x, int y) {
	for (int i = 1; i <= n; i++)
	{
		if (cc[i] == y)
			cc[i] = x;
	}
}


void Kruskal()
{
    int ct = 0;
    int nrm = 0;
    Arb.clear();

    cc.assign(n + 1, 0);        
    for (int i = 1; i <= n; ++i) {
        cc[i] = i;
    }

    sort(G.begin(), G.end());
    for (auto muchie : G) {
        int cost = muchie[0], x = muchie[1], y = muchie[2];
        if (cc[x] == cc[y]) 
        {
            continue;
        }
        ct += cost;
        Arb.push_back(muchie);
        uneste(cc[x], cc[y]);
        ++nrm;
        if (nrm == n - 1) 
        {
            break;
        }
    }

    out << ct << "\n";
    out << Arb.size() << "\n";
    for (auto& muchie : Arb) out << muchie[1] << " " << muchie[2] << "\n";
}

int main()
{
	citire();
	Kruskal();
}