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

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

struct muchie
{
    int from, to, cost;
};

vector<muchie> graf, raspuns;
long long N, M, cost_total, nr_muchii;
int tata_de[200005], lant_maxim[200005];

int findRoot(int x)
{
    if (x == tata_de[x])
        return x;
    return tata_de[x] = findRoot(tata_de[x]);
}

bool compareCosts(muchie a, muchie b)
{
    return a.cost < b.cost;
}

void join(int a, int b)
{
    int tata_a = findRoot(a);
    int tata_b = findRoot(b);
    if (tata_a == tata_b)
        return;
    else if (lant_maxim[tata_a] < lant_maxim[tata_b])
        tata_de[tata_a] = tata_b;
    else if (lant_maxim[tata_a] > lant_maxim[tata_b])
        tata_de[tata_a] = tata_b;
    else if (lant_maxim[tata_a] == lant_maxim[tata_b])
    {
        tata_de[tata_a] = tata_b;
        lant_maxim[tata_a]++;
    }
}

void min_spanning_tree()
{
    for (int i = 0; i < M; i++)
    {
        if (findRoot(graf[i].from) != findRoot(graf[i].to))
        {
            nr_muchii++;
            cost_total += graf[i].cost;
            join(graf[i].from, graf[i].to);
            raspuns.push_back(graf[i]);
        }
    }
}

int main()
{
    fin >> N >> M;
    int X, Y, C;
    for (int i = 1; i <= N; i++)
        tata_de[i] = i, lant_maxim[i] = 1;
    for (int i = 1; i <= M; i++)
    {
        fin >> X >> Y >> C;
        muchie muchie_i;
        muchie_i.from = X;
        muchie_i.to = Y;
        muchie_i.cost = C;
        graf.push_back(muchie_i);
    }
    sort(graf.begin(), graf.end(), compareCosts);
    min_spanning_tree();
    fout << cost_total << "\n" << nr_muchii << "\n";
    for (int i = 0; i < raspuns.size(); i++)
        fout << raspuns[i].from << " " << raspuns[i].to << "\n";
    return 0;
}