#include <fstream>
#include <vector>
#include <algorithm>

#define DIMN 200010
#define DIMM 400010

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {
    int operator< (const muchie &b) const {
        return c < b.c;
    }
    int a, b, c;
};

vector<muchie> V;
vector< pair<int, int> > S;

int T[DIMN];

muchie x;
int n, m, i, ra, rb, cost;

int rad(int x) {
    while(T[x] > 0)
        x = T[x];

    return x;
}

int main() {
    fin>>n>>m;

    for (i=1;i<=m;i++) {
        fin>>x.a>>x.b>>x.c;
        V.push_back(x);
    }

    for (i=1;i<=n;i++)
        T[i] = -1;

    sort(V.begin(), V.end());
    //fout<<n-1<<"\n";
    for (i=0;i<V.size();i++) {
        ra = rad(V[i].a);
        rb = rad(V[i].b);
        if (ra != rb) {
            //fout<<V[i].a<<" "<<V[i].b<<"\n";
            cost += V[i].c;
            S.push_back(make_pair(V[i].a, V[i].b));

            if (T[ra] < T[rb]) {
                T[ra] += T[rb];
                T[rb] = ra;
            } else {
                T[rb] += T[ra];
                T[ra] = rb;
            }
        }
    }
    fout<<cost<<"\n"<<n-1<<"\n";
    for (i=0;i<S.size();i++)
        fout<<S[i].first<<" "<<S[i].second<<"\n";
    return 0;
}