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

using namespace std;

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

struct muchie {
    int x, y, c;
};

int t[20005], h[20005], n, m, cnt;
muchie v[40005];
vector<muchie> final;

bool cmp(const muchie &a, const muchie &b) {
    return a.c < b.c;
}

void init(int a) {
    t[a] = a;
    h[a] = 0;
}

int find(int a){
    if(t[a] != a)
        t[a] = find(t[a]);
    return t[a];
}

void reun(const muchie &a){
    int ra = find(a.x);
    int rb = find(a.y);
    if(ra == rb) return;  // evită ciclurile

    if(h[ra] > h[rb]) {
        t[rb] = ra;
    } else {
        t[ra] = rb;
        if(h[ra] == h[rb])
            h[rb]++;
    }

    cnt += a.c;
    final.push_back(a);
}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        fin >> v[i].x >> v[i].y >> v[i].c;
    }

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

    for(int i = 1; i <= n; i++)
        init(i);

    int nr = 0;
    for(int i = 1; i <= m; i++) {
        if(find(v[i].x) != find(v[i].y)) {
            reun(v[i]);
            nr++;
            if(nr == n - 1) break;
        }
    }

    fout << cnt << '\n' << final.size() << '\n';
    for (size_t i = 0; i < final.size(); i++)
        fout << final[i].x << " " << final[i].y << '\n';

    return 0;
}