#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define NMax 200005

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

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

int fatherOf(int node) {
    int e, aux;
    for (e = node;FA[e] != e;e = FA[e]);
    for (;FA[node] != node;) {
        aux = FA[node];
        FA[node] = e;
        node = aux;
    }

    return e;
}

void join(int a, int b) {
    int fa = fatherOf(a);
    int fb = fatherOf(b);

    if (fa != fb) {
        if (GR[fa] > GR[fb])
            FA[fb] = fa;
        else if (GR[fa] < GR[fb])
            FA[fa] = fb;
        else
            FA[fa] = fb, GR[fb]++;
    }
}

void solve() {
    for (int i=1;i<=n;i++)
        FA[i] = i, GR[i] = 1;

    for (unsigned i=0;i<M.size();i++) {
        int c = M[i].first;
        int a = M[i].second.first;
        int b = M[i].second.second;
        if (fatherOf(a) != fatherOf(b)) {
            join(a, b);
            cost += c;
            arb.pb(mp(a,b));
        }
    }

    g<<cost<<'\n';
    g<<arb.size()<<'\n';
    for (unsigned i=0;i<arb.size();i++) {
        g<<arb[i].first<<' '<<arb[i].second<<'\n';
    }
}

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

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

int main() {

    read();
    solve();

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