#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

struct wEdge {

    int x, y, w;

};

int n, m, a, b, c, cost;
int linkU[200002];
int sizeU[200002];

vector<pair<int, int> > v;

struct compW {


    bool operator() (wEdge x, wEdge y) {

        return x.w > y.w;

    }

};

priority_queue<wEdge, vector<wEdge>, compW> q;

wEdge z;

int findU(int x) {

    while (x != linkU[x]) {
        x = linkU[x];
    }
    return x;

}

bool sameU(int a, int b) {

    return findU(a) == findU(b);

}

void uniteU(int a, int b) {

    a = findU(a);
    b = findU(b);

    if (sizeU[a] < sizeU[b]) {
        swap(a, b);
    }

    sizeU[a] += sizeU[b];
    linkU[b] = a;

}

int main()
{

    fin>>n>>m;

    for (int i=1; i<=m; i++) {

        fin>>a>>b>>c;

        z.x = a;
        z.y = b;
        z.w = c;

        q.push(z);


    }

    for (int i=1; i<=n; i++) {
        linkU[i] = i;
        sizeU[i] = 1;
    }

    while (!q.empty()) {

        z = q.top();
        q.pop();

        a = z.x;
        b = z.y;
        c = z.w;

        if (!sameU(a, b)) {

            uniteU(a, b);
            cost += c;
            v.push_back(make_pair(a, b));

        }

    }

    fout<<cost<<"\n"<<v.size()<<"\n";

    for (int i=0; i<v.size(); i++) {

        fout<<v[i].first<<" "<<v[i].second<<"\n";

    }

    return 0;
}