#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

const int NMAX = 200005;
const int MMAX = 500005;
int n, m, dad[NMAX], maxlen[NMAX];

struct Muchii {
    int a, b, cost;
}v[MMAX];

bool cmp(Muchii x, Muchii y) {
    return x.cost < y.cost;
}

vector<pair<int, int> > arb;

int findad(int x) {
    if(dad[x] == x)
        return x;
    dad[x] = findad(dad[x]);
    return dad[x];
}

void unionfind(int x, int y) {
    if(maxlen[x] > maxlen[y])
        dad[y] = x;
    if(maxlen[x] < maxlen[y])
        dad[x] = y;
    if(maxlen[x] == maxlen[y]) {
        dad[x] = y;
        maxlen[y] ++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    in >> n >> m;
    for(int i = 1; i <= m; i ++)
        in >> v[i].a >> v[i].b >> v[i].cost;
    for(int i = 1; i <= n; i ++) {
        maxlen[i] = 1;
        dad[i] = i;
    }
    sort(v + 1, v + m + 1, cmp);
    int s = 0;
    for(int i = 1; i <= m; i ++) {
        if(findad(v[i].a) != findad(v[i].b)) {
            s += v[i].cost;
            unionfind(dad[v[i].a], dad[v[i].b]);
            arb.push_back({v[i].a, v[i].b});
        }
    }
    out << s << "\n" << arb.size() << "\n";
    for(int i = 0; i < arb.size(); i ++)
        out << arb[i].first << " " << arb[i].second << "\n";
    return 0;
}