#include <cstdio>
#include <algorithm>
using namespace std;
struct Muchie
{
    int u,v,c;
};
Muchie v1[400005];
int t[200005];
int h[200005];
struct Solutie
{
    int x,y;
} sol[200005];
int FindSet(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
bool UnionSet(int x, int y)
{
    int tx,ty;
    tx=FindSet(x);
    ty=FindSet(y);
    if(tx==ty)
        return 0;
    else{
        if(h[tx]==h[ty]){
            h[tx]++;
            t[ty]=tx;
        }
        else{
            if(h[tx]<h[ty])
                t[tx]=ty;
            else
                t[ty]=tx;
        }
        return 1;
    }
}
bool cmp(Muchie a, Muchie b)
{
    return a.c<b.c;
}
int main()
{   freopen("apm.in", "r",stdin);
    freopen("apm.out", "w", stdout);
    int n,m,i,cost=0,k;
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
        scanf("%d%d%d", &v1[i].u, &v1[i].v, &v1[i].c);
    for(i=1; i<=n; i++){
        t[i]=i;
        h[i]=1;
    }
    sort(v1+1, v1+m+1, cmp);
    k=0;
    for(i=1; i<=m; i++)
        if(UnionSet(v1[i].u, v1[i].v)==1){
            cost+=v1[i].c;
            sol[++k].x=v1[i].u;
            sol[k].y=v1[i].v;
        }
    printf("%d\n%d\n", cost, n-1);
    for(i=1; i<=k; i++)
        printf("%d %d\n", sol[i].x, sol[i].y);
    return 0;
}