#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 200000;

int h[NMAX + 1], d[NMAX + 1];

struct muchie {
    int x, y, c;
};

vector<muchie> v;
vector<muchie> sol;

bool cmp(muchie m1, muchie m2) {
    return m1.c < m2.c;
}

void Union(int x, int y) {
    if(h[x] < h[y]) {
        d[x] = y;
    } else {
        if(h[x] > h[y]) {
            d[y] = x;
        } else {
            d[y] = x;
            h[x]++;
        }
    }
}

int Find(int x) {
    int r = x;
    while(r != d[r]) {
        r = d[r];
    }
    return r;
}


int main() {
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        f >> a >> b >> c;
        v.push_back({a, b, c});
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 1; i <= n; i++) {
        h[i] = 1;
        d[i] = i;
    }
    int apm = 0;
    for(int i = 0; i < m; i++) {
        int p = Find(v[i].x);
        int q = Find(v[i].y);
        if(p != q) {
            apm += v[i].c;
            sol.push_back(v[i]);
            Union(p, q);
        }
    }
    g << apm<<endl;
    g<<sol.size()<<endl;
    for(int i = 0; i < sol.size(); i++) {
        g << sol[i].x << ' ' << sol[i].y << '\n';
    }
    return 0;
}