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

const int NMAX = 200000;
int tata[NMAX + 1], h[NMAX + 1];

struct Varf {
    int u, v, w;
};

bool comparareMuchii(Varf a, Varf b) {
    return a.w < b.w;
}

void Initializare(int u) {
    tata[u] = h[u] = 0;
}

int Find(int u) {
    while (tata[u] != 0)
        u = tata[u];
    return u;
}

void Union(int u, int v) {
    int ru, rv;
    ru = Find(u);
    rv = Find(v);
    if (h[ru] > h[rv]) {
        tata[rv] = ru;
    } else {
        tata[ru] = rv;
        if (h[ru] == h[rv]) {
            h[rv]++;
        }
    }
}

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

    int n, m, cost_totat = 0, nr_drumuri = 0;
    f >> n >> m;

    vector<Varf> muchii(m);
    vector<Varf> sol;

    for (int i = 0; i < m; ++i) {
        f >> muchii[i].u >> muchii[i].v >> muchii[i].w;
    }

    sort(muchii.begin(), muchii.end(), comparareMuchii);

    for (int i = 0; i < m; ++i) {
        int u = muchii[i].u;
        int v = muchii[i].v;
        int w = muchii[i].w;

        int ru = Find(u);
        int rv = Find(v);

        if (ru != rv) {
            cost_totat = cost_totat + w;
            nr_drumuri++;
            sol.push_back(muchii[i]);
            Union(ru, rv);
        }
    }

    g << cost_totat << endl;
    g << nr_drumuri << endl;

    for(auto varf : sol) {
        g << varf.v << " " << varf.u << endl;
    }

    f.close();
    g.close();

    return 0;
}