#include <cstdio>
#include <algorithm>

using namespace std;

#define FIN "apm.in"
#define FOUT "apm.out"

#define N 200000
#define M 400000

struct pair2
{
    int first, second, third;
};

int n, m, cost, nr;
int r[N], d[N], a[M];

pair2 v[M];

int root(int x)
{
    if (x == r[x])
        return x;

    r[x] = root(r[x]);

    return r[x];
}

void merge(int x, int y)
{
    if (d[x] > d[y])
        r[y] = x;
    else if (d[x] < d[y])
        r[x] = y;
    else if (x != y)
    {
        r[x] = y;

        ++ d[x];
    }
}

int comp(pair2 x, pair2 y)
{
    return x.third < y.third;
}

int main()
{
    int i;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d", &n, &m);

    for (i = 1; i <= m; ++ i)
        scanf("%d%d%d", &v[i].first, &v[i].second, &v[i].third);

    for (i = 1; i <= n; ++ i)
    {
        r[i] = i;

        d[i] = 1;
    }

    sort(v + 1, v + m + 1, comp);

    for (i = 1; i <= m; ++ i)
        if (root(v[i].first) != root(v[i].second))
        {
            merge(root(v[i].first), root(v[i].second));

            cost += v[i].third;

            a[i] = 1;

            ++ nr;
        }

    printf("%d\n%d\n", cost, nr);

    for (i = 1; i <= m; ++ i)
        if (a[i])
            printf("%d %d\n", v[i].first, v[i].second);
}