/// apm
#include <bits/stdc++.h>
#define NMax 200005

#define mp make_pair
#define pb push_back
#define po pop_back
using namespace std;

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

int n,m;
vector< pair<int, pair<int, int> > >M;
vector< pair<int, pair<int, int> > >S;
int apmcost = 0;
int FA[NMax];
int GR[NMax];

int rootFor(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) {
    int xr = rootFor(x), yr = rootFor(y);
    if (GR[xr] < GR[yr]) {
        FA[xr] = yr;
    } else if (GR[xr] > GR[yr]) {
        FA[yr] = xr;
    } else {
        FA[yr] = xr;
        GR[xr]++;
    }
}

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

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

void init() {
    apmcost = 0;
    for (int i=1;i<=n;i++) {
        FA[i] = i;
        GR[i] = 1;
    }
}

void output() {
    g<<apmcost<<'\n';
    g<<S.size()<<'\n';
    for (auto it = S.begin(); it!=S.end();it++)
        g<<(*it).second.first<<' '<<(*it).second.second<<'\n';
}

void solve() {
    int connected = 0;
    for (unsigned i=0;i<M.size();i++) {
        if (connected == n-1)
            break;

        int x = M[i].second.first, y = M[i].second.second;
        if (rootFor(x) != rootFor(y)) {
            join(x,y);
            apmcost += M[i].first;
            connected++;
            S.pb(M[i]);
        }
    }
}

int main() {

    read();
    init();
    solve();
    output();

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