#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 100001
using namespace std;

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

vector< pair<int, pair<int,int>> > cost_muchie; // m.first == costul, m.second.first = x, m.second.second = y;
vector<pair<int,int>> sol;          // pornim cu un arbore vid si testam muchiile grafului dat, pe rand, pt a sti daca le add in APCM sau nu
int n, m, tata[Nmax], rang[Nmax];                                                               // daca au cost minim sau nu

void init() {
    for (int i=0; i<n; i++) {
        tata[i] = i; // parintele
        rang[i] = 1; // dimensiunea arborelui (cati copii are in total) => initial fiecare nod reprez un arbore form doar din rad
    }
}

int find (int x)
{
    while (x!=tata[x]) {
        x = tata[x];
        //find(x);
    }
    return x;
}

void uneste(int x, int y) // reuniune dupa rang <=> atasez arborelui mai mare pe cel mai mic
{
    x = find(x);
    y = find(y);

    if (rang[x] >= rang[y]) {
        tata[y] = x;
        rang[x] += rang[y];
    }
    else {
        tata[x] = y;
        rang[y] += rang[x];
    }
}


int Kruskal()
{
    int cost = 0;
    sort(cost_muchie.begin(), cost_muchie.end()); // sortez muchiile in ordine crescatoare dupa cost
    for (auto muchie: cost_muchie)
    {                                       // pentru fiecare muchie
        if (find(muchie.second.first) != find(muchie.second.second))    // daca nodurile care o formeaza nu fac deja parte din aceeasi componenta (arbore)
        {                                                                                   // ca sa nu ajungem sa formam cicluri ca n-ar mai fi arbore
            sol.push_back(muchie.second);
            uneste(muchie.second.first, muchie.second.second);      // atunci le unim (formam muchia in APCM)
            cost += muchie.first;                                   // actualizam costul
        }
    }
    return cost;
}


int main()
{
    int x, y, cost;
    fin >> n >> m;
    for (int i=0; i<m; i++)
    {
        fin >> x >> y >> cost;
        cost_muchie.push_back(make_pair(cost, make_pair(x,y)));
    }

    init();

    fout << Kruskal() << "\n" << sol.size() << "\n";
    for (int i=0; i<sol.size(); i++)
    {
        fout << sol[i].first << " " << sol[i].second << "\n";
    }

    return 0;
}