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

using namespace std;

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

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

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 ++) w[i] = i;

    int C = 0, k = 1;
    for(vector<muchie>::iterator p = M.begin(); p != M.end() && k < n; p ++) {
        aux = *p;
        if(w[aux.x] != w[aux.y]) {
            k ++;
            int what = w[aux.x];
            for(int j = 1; j <= n; j ++)
                if(w[j] == what)
                    w[j] = w[aux.y];
            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;
}