/// Kruskal, O(M * log(N))
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct Edge {
    int x, y, cost;
};

int n, m, i, j, rad1, rad2, cmin;
int h[200005], rad[200005];
Edge mc[400005];
vector<pair<int, int>> apcm;

bool cmp(Edge e1, Edge e2) {
    return e1.cost <= e2.cost;
}

int root(int x) {
    while(rad[x] != 0)
        x = rad[x];
    return x;
}

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

    f >> n >> m;
    for(i = 0; i < m; i++)
        f >> mc[i].x >> mc[i].y >> mc[i].cost;
    f.close();

    sort(mc + 0, mc + m, cmp);  /// sortez muchiile dupa cost
    for(i = 1; i <= n; i++) {
        rad[i] = 0;    /// reprezentantul subarborelui in care se afla i
        h[i] = 0;      /// inaltimea componentei din care face parte nodul i
    }

    j = 0;      /// numar de muchii introduse in apcm
    cmin = 0;   /// costul arborelui
    for(i = 0; i < m; i++) {
        rad1 = root(mc[i].x);
        rad2 = root(mc[i].y);                       /// radacinile extremitatilor
        if(rad1 != rad2) {                          /// aleg muchia daca extremitatile sale sunt in componente diferite
            apcm.emplace_back(mc[i].x, mc[i].y);    /// adaug muchia in arbore
            cmin += mc[i].cost;                     /// cresc costul arborelui
            if(h[rad1] > h[rad2])                   /// adaug componenta cu inaltime mai mica la cea cu inaltime mai mare
                rad[rad2] = rad1;
            else {
                rad[rad1] = rad2;
                if(h[rad1] == h[rad2])
                    h[rad2]++;
            }
            j++;
            if(j == n - 1)
                break;
        }
    }

    g << cmin << '\n' << n - 1 << '\n';
    for(i = 0; i < apcm.size(); i++)
        g << apcm[i].first << ' ' << apcm[i].second << '\n';
    g.close();

    return 0;
}