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

using namespace std;

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

int n, m, a, b, c;

int link[200002];
int sizeU[200002];

struct wEdge {

    int x, y, w;

};

struct compW {

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

        return x.w > y.w;

    }

};

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

wEdge z;

vector<pair<int, int> > v;

int findU(int x) {

    while (x != link[x]) {
        x = link[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];
    link[b] = a;

}

long long sum;

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++) {
        link[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);

            sum += c;

            v.push_back(make_pair(a, b));

        }

    }

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

    for (int i=0; i<v.size(); i++) {
        fout<<v[i].first<<" "<<v[i].second<<"\n";
    }

    return 0;
}