#include <bits/stdc++.h>
using namespace std;

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

struct muchie {
    int x, y, cost;
} v[400005];

bool cmp(muchie a, muchie b) {
    return a.cost < b.cost;
}

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

    sort(v + 1, v + 1 + m, cmp);
    int t[200002], total = 0;
    for(int i = 1; i <= n; i++) t[i] = i;
    vector<muchie> muchii;

    for(int i = 1; i <= m; i++) {
        if(t[v[i].x] != t[v[i].y]) {
            total += v[i].cost;
            muchii.push_back(v[i]);

            int ax = t[v[i].x], ay = t[v[i].y];
            for(int j = 1; j <= n; j++) {
                if(t[j] == ay) {
                    t[j] = ax;
                }
            }
        }
    }

    fout << total << '\n' << n - 1 << '\n';
    for(auto i : muchii) {
        fout << i.x << " " << i.y << '\n';
    }
    return 0;
}