#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 1e5;
int tati[NMAX + 2], d[NMAX + 2];
int n, m, q, a, b, cost;
struct Alex {
    int a, b, c;
}muchii[4 * NMAX + 2];
vector<pair<int, int>> ans;
bool comp(Alex a, Alex b) {
    return a.c < b.c;
}
int find(int x) {
    if(tati[x] == x)
        return x;
    else
        return find(tati[x]);
}
void alipire(int x, int y) {
    if(d[x] == d[y]) {
        d[x]++;
        tati[y] = x;
    } else if(d[x] < d[y]) {
        tati[x] = y;
    } else {
        tati[y] = x;
    }
}
int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        tati[i] = i;
        d[i] = 1;
    }
    for(int i = 1; i <= m; i++) {
        cin >> a >> b >> q;
        muchii[i].a = a;
        muchii[i].b = b;
        muchii[i].c = q;
    }
    sort(muchii + 1, muchii + 1 + m, comp);
    for(int i = 1; i <= m; i++) {
        int x = find(muchii[i].a);
        int y = find(muchii[i].b);
        if(x != y) {
            alipire(x, y);
            ans.push_back(make_pair(muchii[i].a, muchii[i].b));
            cost += muchii[i].c;
        }
    }
    cout << cost << "\n" << ans.size() << "\n";
    vector<pair<int, int>>:: iterator it;
    for(it = ans.begin(); it != ans.end(); ++it)
        cout << it -> second << " " << it -> first << "\n";
    return 0;
}