#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

vector <int> g[200010];
int t[200010], mi[200010], ap[400010];

struct muchie
{
    int a, b, cost;
} v[400010];

void dfs (int nod, int chestie)
{
    t[nod] = chestie;

    for (auto &it : g[nod])
        if (!t[it]) dfs (it, chestie);
}

int main ()
{
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);

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

    for (int i = 1; i <= m; ++i)
    {
        scanf ("%d %d %d", &v[i].a, &v[i].b, &v[i].cost);
        t[i] = i;
    }

    int nr = n, rez = 0;
    bool OK = true;
    for (; OK;)
    {
        OK = false;
        for (int i = 1; i <= nr; ++i)
            mi[i] = -1;

        for (int i = 1; i <= m; ++i)
        {
            int u = v[i].a;
            int w = v[i].b;

            if (t[u] == t[w]) continue;

            if (mi[t[u]] == -1 || v[i].cost < v[ mi[t[u]] ].cost)
                mi[t[u]] = i;

            if (mi[t[w]] == -1 || v[i].cost < v[ mi[t[w]] ].cost)
                mi[t[w]] = i;
        }

        for (int i = 1; i <= nr; ++i)
            if (mi[i] != -1 && !ap[ mi[i] ])
            {
                OK = true;

                int u = v[ mi[i] ].a;
                int w = v[ mi[i] ].b;

                ap[ mi[i] ] = 1;
                g[u].push_back (w);
                g[w].push_back (u);
                rez += v[ mi[i] ].cost;
            }

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

        for (int i = 1; i <= n; ++i)
            if (!t[i])
                dfs (i, ++nr);
    }

    printf ("%d\n%d\n", rez, n - 1);

    for (int i = 1; i <= m; ++i)
        if (ap[i]) printf ("%d %d\n", v[i].a, v[i].b);

    return 0;
}