#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int Nmax = 200005, Mmax = 400005;

int n, m, cost_min, F[Nmax], a[Nmax], b[Nmax];

struct muchie{
    int X, Y, cost;
    bool operator<(const muchie &A)const
    {
        return cost<A.cost;
    }
};

muchie v[Mmax];

int find_root(int nod){
    if(F[nod] < 0){
        return nod;
    }
    int root = find_root(F[nod]);
    F[nod] = root;
    return root;
}

void glue(int nod1, int nod2){
    int r1 = find_root(nod1);
    int r2 = find_root(nod2);

    if(F[r1] < F[r2]){
        swap(F[r1], F[r2]);
    }
    F[r2] += F[r1];
    F[r1] = r2;
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> v[i].X >> v[i].Y >> v[i].cost;
    }
    for(int i = 1; i <= n; i++){
        F[i] = -1;
    }
    sort(v+1, v+m+1);
    int j = 0;
    for(int i = 1; i <= m; i++){
        if(find_root(v[i].X) != find_root(v[i].Y)){
            glue(v[i].X, v[i].Y);
            a[j] = v[i].X;
            b[j] = v[i].Y;
            j++;
            cost_min += v[i].cost;
        }
    }
    fout << cost_min << endl << j << endl;
    for(int i = 0; i < j; i++){
        fout << a[i] << ' ' << b[i] << endl;
    }

    return 0;
}