#include<bits/stdc++.h>

using namespace std;

const int nMax = 200001, mMax = 400001;

struct element{
    int x, y, val;
}v[mMax];
int t[nMax], n, m, cnt, sx[nMax], sy[nMax];

bool cmp (element a, element b){
    return a.val < b.val;
}

int rad(int x){
    if(t[x] == 0)
        return x;

    int r = rad(t[x]);
    t[x] = r;

    return r;
}

int main (){
    FILE *in = fopen("apm.in","r");

    fscanf(in,"%d%d", &n, &m);

    for(int i = 0 ; i < m ; i++){
        fscanf(in,"%d%d%d", &v[i].x, &v[i].y, &v[i].val);
        //v[i].x--, v[i].y--;
    }

    sort(v, v + m, cmp);

    int rx, ry, sum = 0;

    for(int i = 0 ; i < m ; i++){

        rx = rad(v[i].x);
        ry = rad(v[i].y);

        if(rx != ry){
            t[rx] = ry;
            sx[cnt] = v[i].x;
            sy[cnt++] = v[i].y;
            sum += v[i].val;
        }
    }

    FILE *out = fopen("apm.out","w");

    fprintf(out,"%d\n%d\n", sum, cnt);
    for(int i = 0 ; i < cnt ; i++){
        fprintf(out,"%d %d\n", sx[i] + 1, sy[i] + 1);
    }

    return 0;
}