/// apm
#include <iostream>
#include <fstream>
#include <algorithm>

#define NMax 200005
#define pb push_back

struct muchie {
    int x,y,c;
    muchie() {}
    muchie(int x, int y, int c) {
        this->x = x;
        this->y = y;
        this->c = c;
    }
};

using namespace std;

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

int n,m;
int FA[NMax];
int GR[NMax];
vector<muchie> M;
int cost = 0;
vector<muchie> sol;

/**  Paduri de multimi disjuncte **/
int fatherOf(int x) {
    int e, aux;
    for (e = x; FA[e] != e; e = FA[e]);

    for (;FA[x]!=x;) {
        aux = FA[x];
        FA[x] = e;
        x = aux;
    }

    return e;
}

void join(int x, int y) {
    if (GR[x] < GR[y])
        FA[x] = y;
    else if (GR[x] > GR[y])
        FA[y] = x;
    else {
        FA[y] = x;
        GR[x]++;
    }
}

bool cmp(const muchie &a, const muchie &b) {
    return (a.c < b.c);
}

void read() {
    f>>n>>m;
    for (int i=1;i<=m;i++) {
        int x, y, c;
        f>>x>>y>>c;
        M.pb(muchie(x,y,c));
    }

    sort(M.begin(), M.end(), cmp);
}

void solve() {
    for (int i=1;i<=n;i++) {
        FA[i] = i;
        GR[i] = 1;
    }
    for (unsigned i=0;i<M.size();i++) {
        muchie muc = M[i];
        if (fatherOf(muc.x) != fatherOf(muc.y)) {
            cost += muc.c;
            sol.pb(muc);
            join(fatherOf(muc.x), fatherOf(muc.y));
        }
    }

    g<<cost<<'\n';
    g<<sol.size()<<'\n';
    for (unsigned i=0;i<sol.size();i++)
        g<<sol[i].x<<' '<<sol[i].y<<'\n';
}

int main() {

    read();
    solve();

    f.close(); g.close();
    return 0;
}