#include <fstream>
#include <algorithm>

using namespace std;

struct MUCHIE{
    int x, y, c, sel;
};

const int NMAX = 200000;
int t[NMAX], h[NMAX + 5];
MUCHIE v[400005];
ifstream fin("apm.in");
ofstream fout("apm.out");

bool cmp(MUCHIE a, MUCHIE b){
    return a.c < b.c;
}

int FindSet(int x){
    while(t[x] != x)
        x = t[x];
    return x;
}

void UnionSet(int x, int y){
    if(h[x] > h[y]){
        t[y] = x;
    }
    else{
        if(h[y] > h[x]){
            t[x] = y;
        }
        else{
            t[y] = x;
            h[x]++;
        }
    }
}

int main()
{
    int n, m, i, cost, nr, x, y, tx, ty;
    fin >> n >> m;
    for(i = 1; i <= n; i++){
        t[i] = i;
        h[i] = 1;
    }
    for(i = 1; i <= m; i++)
        {fin >> v[i].x >> v[i].y >> v[i].c; v[i].sel = 0;}
    sort(v + 1, v + m + 1, cmp);
    cost = 0; nr = 0;
    for(i = 1; i <= m && nr < n - 1; i++){
        x = v[i].x; y = v[i].y;
        tx = FindSet(x);
        ty = FindSet(y);
        if(tx != ty){
            UnionSet(tx, ty);
            nr++;
            cost = cost + v[i].c;
            v[i].sel = 1;
        }
    }
    fout << cost << "\n";
    fout << n - 1 << "\n";
    for(i = 1; i <= m; i++)
        if(v[i].sel == 1)
            fout << v[i].x << " " << v[i].y << "\n";
    fin.close(); fout.close();
    return 0;
}