#include<stdio.h>
#include<vector>
#include<algorithm>
#define NMAX 200005
#define EMAX 400005
using namespace std;

struct vertex{
    int cost, x, y;
} vec[EMAX];

vector<int> apm;
int N, M, componente[NMAX], costAPM;

bool cmp(vertex a, vertex b){
    if(a.cost < b.cost){
        return true;
    }
    return false;
}

int minimum(int a, int b){
    if(a < b){
        return a;
    }
    return b;
}
int maximum(int a, int b){
    if(a < b){
        return b;
    }
    return a;
}

int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int i, j, x, y, c;
    scanf("%d%d", &N, &M);
    for(i = 1; i <= M; i++){
        scanf("%d%d%d", &vec[i].x, &vec[i].y, &vec[i].cost);
    }
    for(i = 1; i <= N; i++){
        componente[i] = i;
    }
    sort(vec + 1, vec + M + 1, cmp);
    int NrMSel = 0, m, m2;
    for(i = 1; NrMSel < N - 1; i++){
        if(componente[vec[i].x] != componente[vec[i].y]){
            apm.push_back(i); NrMSel++;
            costAPM += vec[i].cost;
            m = minimum(componente[vec[i].x], componente[vec[i].y]);
            m2 = maximum(componente[vec[i].x], componente[vec[i].y]);
            for(j = 1; j <= N; j++){
                if(componente[j] == m2){
                    componente[j] = m;
                }
            }
        }
    }
    printf("%d\n%d\n", costAPM, apm.size());
    for(i = 0; i < apm.size(); i++){
        printf("%d %d\n", vec[apm[i]].x, vec[apm[i]].y);
    }

}