#include <cstdio>
#include <algorithm>

using namespace std;

int tata[200005];
int depth[200005];
pair<int, pair<int, int> > muchii[400005];
pair<int, int> sol[200005];
int nr = 0;
int s = 0;

int n, m;

void citire(){
    scanf("%d %d", &n, &m);

    int tmp1, tmp2, tmp3;

    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &tmp1, &tmp2, &tmp3);

        muchii[i] = {tmp3, {tmp1, tmp2}};
    }
}

int getTata(int x){
    int xx = x;

    while(tata[x] != x){
        x = tata[x];
    }

    tata[xx] = x;

    return x;
}

void unire(int x, int y){
    x = getTata(x);
    y = getTata(y);

    if(depth[x] < depth[y]){
        tata[x] = y;
    }
    else if(depth[x] > depth[y]){
        tata[y] = x;
    }
    else{
        tata[y] = x;
        depth[x]++;
    }
}

bool suntUnite(int x, int y){
    if(getTata(x) == getTata(y)){
        return true;
    }

    return false;
}

void initializare(){
    for(int i = 0; i < n; i++){
        tata[i] = i;
        depth[i] = 1;
    }

    sort(muchii, muchii + m);
}

void solve(){
    for(int i = 0; i < m; i++){
        if(suntUnite(muchii[i].second.first, muchii[i].second.second)){
            continue;
        }
        else{
            unire(muchii[i].second.first, muchii[i].second.second);
            sol[nr] = muchii[i].second;
            nr++;
            s += muchii[i].first;
        }
    }

    printf("%d\n%d\n", s, n - 1);

    for(int i = 0; i < nr; i++){
        printf("%d %d\n", sol[i].first, sol[i].second);
    }
}

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

    citire();
    initializare();
    solve();

    return 0;
}