#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector<muchie> M, S;
int t[200010];

int tata(int x) {
    if(t[x] == x) return x;
    t[x] = tata(t[x]);
    return t[x];
}

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

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

    int n, m;
    f >> n >> m;

    int x, y, z;
    muchie aux;
    for(int i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        aux.x = x;
        aux.y = y;
        aux.z = z;
        M.push_back(aux);
    }
    sort(M.begin(), M.end(), cmp);

    for(int i = 1; i <= n; i ++) t[i] = i;

    int C = 0, k = 1;
    for(vector<muchie>::iterator p = M.begin(); p != M.end() && k < n; p ++) {
        aux = *p;
        int tx = tata(aux.x);
        int ty = tata(aux.y);
        if(tx != ty) {
            k ++;
            t[tx] = ty;
            S.push_back(aux);
            C += aux.z;
        }
    }

    g << C << "\n" << n - 1 << "\n";
    for(int i = 0; i < S.size(); i ++)
        g << S[i].x << " " << S[i].y << "\n";
    return 0;
}