#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back

using namespace std;
const int maxn = 5e5 + 5;
int n, m;

ifstream f("apm.in");
ofstream g("apm.out");

struct xy {
    int x, y;
};
vector <xy> v[maxn];
struct muchie {
    int x, y, cost;
};
vector<muchie> mc;
bool cmp(muchie a, muchie b) {
    return a.cost < b.cost;
}

int tt[maxn];
int rad(int x) {
    while(x != tt[x]) {
        x = tt[x];
    }
    int tata = x, next;
    while(x != tt[x]) {
        next = tt[x];
        tt[x] = tata;
        x = next;
    }
    return tt[x];
}
void unite(int x, int y) {
    tt[x] = tt[y];
}
int ans = 0;
vector<xy> vans;
int main() {
    int i, j, x, y, z;

    f >> n >> m;
    for(i = 1; i <n; i ++) {
        tt[i] = i;
    }
    for(i = 1; i <= m ; i ++) {
        f >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
        mc.pb({x, y, z});
    }
    sort(mc.begin(), mc.end(), cmp);
    for(auto u : mc) {
        muchie now = u;
        if(rad(now.x) != rad(now.y)) {
            unite(rad(now.x), rad(now.y));
            ans += now.cost;
            vans.pb({now.x, now.y});
        }
    }
    g << ans << '\n';
    g << n - 1 << '\n';
    for(auto u : vans)
        g << u.x << ' ' << u.y << '\n';

    f.close();
    g.close();
    return 0;
}