#include <bits/stdc++.h>
#define inf 2147483647

using namespace std;

struct much{
    int c;
    int x, y;
};
much M[400005];

int t[400005];
int mNr[400005];

int tata(int x) {
    if(t[x] == x)
        return x;
    t[x] = tata(t[x]);
    return t[x];
}

void uneste(int x, int y) {
    t[tata(x)] = tata(y);
}

bool cmp(int A, int B) {
    return M[A].c < M[B].c;
}

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

    int n, m, X, Y, C;

    f >> n >> m;
    for(int i = 1; i <= m; i ++) {
        f >> X >> Y >> C;
        M[i].x = X;
        M[i].y = Y;
        M[i].c = C;
        mNr[i] = i;
    }

    for(int i = 1; i <= n; i ++)
        t[i] = i;

    sort(mNr + 1, mNr + m + 1, cmp);

    int ret = 0;
    vector< pair<int, int> > muchie;

    for(int j = 1; j <= m; j ++) {
        int i = mNr[j];
        if(tata(M[i].x) != tata(M[i].y)) {
            ret += M[i].c;
            uneste(M[i].x, M[i].y);
            muchie.push_back(make_pair(M[i].x, M[i].y));
            if(muchie.size() == (n - 1))
                j = m + 1;
        }
    }
    g << ret << "\n";
    g << n - 1 << "\n";
    for(int i = 0; i < muchie.size(); i ++) {
        g << muchie[i].first << " " << muchie[i].second << "\n";
    }
    return 0;
}