#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 root(int x){
    if(componente[x] == x){
        return x;
    }else{
        int r = root(componente[x]);
        componente[x] = r;
        return r;
    }
}

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, r1 , r2;
    for(i = 1; NrMSel < N - 1; i++){
        r1 = root(vec[i].x);
        r2 = root(vec[i].y);
        if(r1 != r2){
            apm.push_back(i); NrMSel++;
            costAPM += vec[i].cost;
            componente[r1] = r2;
        }
    }
    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);
    }

}