#include<stdio.h>
#include<algorithm>
#include<vector>

#define NMAX 500007

using namespace std;

struct apm{
    int x;
    int y;
    int c;
    inline bool operator < (const apm & dr) const {
        return c < dr.c;
    }
};

apm a[NMAX];
int t[NMAX], h[NMAX], n, m, Sum;
vector< pair<int, int> > sol;

inline int father(int x){
    if(x == t[x])
        return x;
    return father(t[x]);
}

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

int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++ i)
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].c);
    sort(a + 1, a + m + 1);
    for(int i = 1; i <= n; ++ i){
        h[i] = 1;
        t[i] = i;
    }
    for(int i = 1; i <= m; ++ i){
        int tx = father(a[i].x);
        int ty = father(a[i].y);
        if(tx != ty){
            unite(tx, ty);
            sol.push_back(make_pair(a[i].x, a[i].y));
            Sum += a[i].c;
        }
    }
    printf("%d\n", Sum);
    printf("%d\n", sol.size());
    for(int i = 0; i < sol.size(); ++ i)
        printf("%d %d\n", sol[i].first, sol[i].second);
    return 0;
}