#include <cstdio>
#include <algorithm>
#define N 200003
#define M 400003

using namespace std;

struct muchie
{
    int x, y, c;
} v[M];

int n, m, x, y, c, tata[N], ordine[M], Suma, in_pana_mea[N], k;

void pune()
{
    for (int i = 1; i <= n; ++ i)
        tata[i] = i;
}

int reuniune(int nod)
{
    if (tata[nod] == nod)
        return nod;
    return tata[nod] = reuniune (tata[nod]);
}

bool cmp(int i, int j)
{
    if (v[ordine[i]].c > v[ordine[j]].c)
        return false;
    return true;
}

void afisare()
{
    printf ("%d\n%d\n", Suma, n - 1);
    for (int i = 0; i < k; ++ i)
        printf ("%d %d\n", v[in_pana_mea[i]].y, v[in_pana_mea[i]].x);
}

int main()
{
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    scanf ("%d %d ", &n, &m);
    pune();
    for (int i = 1; i <= m; ++ i)
    {
        scanf ("%d %d %d ", &v[i].x, &v[i].y, &v[i].c);
        ordine[i] = i;
    }
    sort (ordine + 1, ordine + m + 1, cmp);
    for (int i = 1; i <= m; ++ i)
        if (reuniune (v[ordine[i]].x) != reuniune (v[ordine[i]].y))
        {
            tata[reuniune (v[ordine[i]].y)] = reuniune (v[ordine[i]].x);
            Suma += v[ordine[i]].c;
            in_pana_mea[k ++] = ordine[i];
        }
    afisare();
    return 0;
}