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

using namespace std;

vector <pair <int, pair<int, int> > > v;
const int INF = 0x3f3f3f3f;

int rad[200002], h[200002];


int find(int x) {
    if (x != rad[x]) {
        rad[x] = find(rad[x]);
    }

    return rad[x];
}


void _union(int x, int y) {
    int radx = find(x);
    int rady = find(y);
    if (radx == rady) {
        return;
    }

    if (h[radx] < h[rady]) {
        rad[radx] = rad[rady];
    } else if (h[radx] > h[rady]) {
        rad[rady] = rad[radx];
    } else {
        rad[radx] = rad[rady];
        h[radx] ++;
    }
}

int main () {
    int n, m;
    ifstream cin("apm.in");
    ofstream cout ("apm.out");
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        rad[i] = i;
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back(make_pair(c, make_pair(a, b)));
    }

    sort(v.begin(), v.end());

    int sum = 0;
    vector <pair<int, int> > sol;
    for (int i = 0; i < m; i++) {
        if (find(v[i].second.first) != find(v[i].second.second)) {
            _union(v[i].second.first, v[i].second.second);
            sum += v[i].first;
            sol.push_back(v[i].second);
        }
    }

    cout << sum << "\n";
    cout << sol.size() << "\n";

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

    return 0;
}