#include <cstdio>
#include <algorithm>

const int maxn = 200001;
const int maxm = 400001;

FILE *in = fopen("apm.in","r"), *out = fopen("apm.out","w");

struct muchie
{
    int x, y, cost;
};

int n, m;
muchie a[maxm], apm[maxm];
int t[maxn], rang[maxn];

bool cmp(muchie m1, muchie m2)
{
    return m1.cost < m2.cost;
}

void read()
{
    fscanf(in, "%d %d", &n, &m);

    for ( int i = 1; i <= m; ++i )
        fscanf(in, "%d %d %d", &a[i].x, &a[i].y, &a[i].cost);
}

void merge(int x, int y)
{
    if ( rang[x] == rang[y] )
    {
        ++rang[x];
        t[y] = x;
    }
    else if ( rang[x] > rang[y] )
        t[y] = x;
    else
        t[x] = y;
}

int find(int x)
{
    if ( t[x] == x )
        return x;

    t[x] = find(t[x]);

    return t[x];
}

int main()
{
    read();

    std::sort(a+1, a+m+1, cmp);

    for ( int i = 1; i <= n; ++i )
        t[i] = i;

    int k = 0, s = 0;
    for ( int i = 1; i <= m; ++i )
        if ( find(a[i].x) != find(a[i].y) )
        {
            apm[++k] = a[i];
            merge(find(a[i].x), find(a[i].y));
            s += a[i].cost;
        }

    fprintf(out, "%d\n%d\n", s, n-1);

    for ( int i = 1; i <= k; ++i )
        fprintf(out, "%d %d\n", apm[i].x, apm[i].y);


    return 0;
}