#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX_N 200005
#define MAX_M 400005

#ifdef _HOME_
#undef MAX_N
#undef MAX_M
#define MAX_N 100
#define MAX_M 100
#endif

int C[MAX_M], X[MAX_M], Y[MAX_M], I[MAX_M];
int TT[MAX_N], ANS[MAX_N];
int N, M, Rez;

void citire()
{
    scanf("%d %d",&N, &M);

    for(int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d",X+i, Y+i, C+i);
        I[i] = i;
    }

    for(int i = 1; i <= N; ++i)
        TT[i] = i;
}

int find(int x)
{
    int R, y;
    for(R = x; R != TT[R]; R = TT[R]);

    while(x != TT[x])
    {
        y = TT[x];
        TT[x] = R;
        x = y;
    }
    return R;
}

void unite(int x, int y)
{
    TT[x] = y;
}

struct cmp
{
    bool operator ()(int i, int j)
    {
        return (C[i] < C[j]);
    }
};

void solve()
{
    sort(I+1, I+M+1, cmp());

    int ind = 0;
    for(int i = 1; i <= M; ++i)
    {
        if(find(X[I[i]]) == find(Y[I[i]])) continue;

        Rez += C[I[i]];
        unite(find(X[I[i]]), find(Y[I[i]]));
        ANS[++ind] = I[i];
    }

    printf("%d\n%d\n", Rez, ind);

    for(int i = 1; i <= ind; ++i)
        printf("%d %d\n",X[ANS[i]], Y[ANS[i]]);
}

int main()
{
    freopen("apm.in","rt",stdin);
    freopen("apm.out","wt",stdout);

    citire();
    solve();
}