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

using namespace std;

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

//ifstream in("grafpond.in");
//ofstream out("grafpond.out");


int r[200001];
int n, m;

struct grf{
    int x;
    int y;
    int cost;
};

bool compare(grf j, grf i) {
    return (i.cost > j.cost);
}

void Reuneste(int u, int v) {
    int r1 = r[u];
    int r2 = r[v];
    for (int k = 1; k <= n; k++)
        if (r[k] == r2)
            r[k] = r1;
}

int main() {

    in >> n >> m;
    grf graf[400001];
    for (int i = 0; i < m; i++) {
        in >> graf[i].x >> graf[i].y >> graf[i].cost;
    }
    sort(graf, graf+m, compare);

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

    int cost = 0;
    int nrmsel = 0;

    vector<pair<int,int>> apm;

    for (int i = 0; i < m; i++) {
        if (r[graf[i].x] != r[graf[i].y]) {
            Reuneste(graf[i].x, graf[i].y);
            apm.emplace_back(graf[i].x, graf[i].y);
            cost += graf[i].cost;
            nrmsel++;
            if (nrmsel == n - 1)
                break;
        }
    }
    out << cost<<endl <<nrmsel <<endl;
    for (int i=0;i<nrmsel;i++){
        out<<apm[i].first<<" "<<apm[i].second<<endl;
    }
    return 0;
}