#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int n, m;
int t[1000005], inalt[1000005];
int x, y, c, ctot;

vector < pair < int , pair < int , int > > > v;
/// retinem muchiile sub forma: {cost, {n1, n2}} 

vector < pair < int , int > > res;

int rad(int nod) {
    if (nod == t[nod])
        return nod;
    int rnod = rad(t[nod]);
    t[nod] = rnod;
    return rnod;
}

void reuniune() {
    int rx = rad(x);
    int ry = rad(y);
    if (inalt[rx] > inalt[ry]) {
        t[ry] = rx;
    }
    else if (inalt[ry] > inalt[rx]) {
        t[rx] = ry;
    }
    else {
        t[ry] = rx;
        inalt[rx]++;
    }
}

bool interogare() {
    return (rad(x) == rad(y));
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    cin >> n >> m;
    for (int i=1;i<=n;i++) 
        t[i] = i;
    for (int i=1;i<=m;i++) {
        cin >> x >> y >> c;
        v.push_back({c, {x, y}});
    }
    sort(v.begin(), v.end());
    for (auto k:v) {
        x = k.second.first;
        y = k.second.second;
        if (!interogare()) {
            reuniune();
            ctot += k.first;
            res.push_back({x, y});
        }
    }
    cout << ctot << '\n';
    cout << res.size() << '\n'; /// cout << n-1 << '\n' ;
    for (auto k:res) {
        cout << k.first << " " << k.second << '\n';
    }
    return 0;
}