#include <cstdio>
#include <algorithm>
#define DIM 200020
using namespace std;
FILE *fin=freopen("apm.in","r",stdin);
FILE *fout=freopen("apm.out","w",stdout);

int N1[DIM], N2[DIM], Price[DIM], Order[DIM], Father[DIM], R[DIM * 2];
int m, n, nr;

inline bool cmp(int i, int j)
{
    return ( Price[i] < Price[j] );
}

void Read()
{
    scanf("%d %d ", &n, &m);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d ", &N1[i], &N2[i], &Price[i]);
        Order[i] = i;
        Father[i] = i;
    }

    sort(Order + 1, Order + m + 1, cmp);

}

inline int Group(int x)
{
    if( x != Father[x] )
        Father[x] = Group(Father[x]);
    return Father[x];
}

inline void Unite(int x, int y)
{
    Father[Group(x)] = Group(y);
}

void Solve()
{
    int priceCount = 0;
    for(int i = 1; i <= m ; ++i)
        if( Group( N1[Order[i]] ) != Group( N2[Order[i]] ) )
        {
            priceCount += Price[Order[i]];
            Unite( N1[Order[i]] , N2[Order[i]] );
            R[++nr] = Order[i];
        }
    printf("%d\n%d\n", priceCount, nr);
    for(int i = 1; i <= nr; ++i)
        printf("%d %d\n", N2[R[i]], N1[R[i]]);
}

int main()
{
    Read();
    Solve();
    return 0;
}