#include <algorithm>
#include <cstdio>
using namespace std;

struct MK {
    int a, b, cost;
    bool operator < (MK arg) const {
        return cost < arg.cost;
    }
};

struct NOD {
    int papa, size;
    NOD() {
        papa = 0;
        size = 1;
    }
};

NOD  v[200005];
MK   g[400005];
bool f[400005];

inline int anc(int arg){
    while(v[arg].papa)
        arg = v[arg].papa;
    return arg;
}

inline void unite(int a, int b){
    a = anc(a);
    b = anc(b);
    if(v[a].size > v[b].size){
        v[a].size += v[b].size;
        v[b].size = 0;
        v[b].papa = a;
    }
    else {
        v[b].size += v[a].size;
        v[a].size = 0;
        v[a].papa = b;
    }
}

int main(void){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,ans=0;

    scanf("%d%d",&n,&m);
    for(int i=0; i<m; ++i) {
        scanf("%d%d%d",&g[i].a,&g[i].b,&g[i].cost);
    }
    sort(g, g+m);

    for(int i=0; i<m; ++i) {
        if(anc(g[i].a)==anc(g[i].b))
            continue;
        unite(g[i].a, g[i].b);

        ans+=g[i].cost;
        f[i]=1;
    }

    printf("%d\n",ans);
    printf("%d\n",n-1);
    for(int i=0; i<m; ++i)
        if(f[i])
            printf("%d %d\n",max(g[i].a, g[i].b),min(g[i].a, g[i].b));
    return 0;
}