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

using namespace std;

vector<tuple<int, int, int> > vecini;
int n, m;

class PaduriDisjuncte
{
private:
    int adancime[200005];
    int parinte[200005];


    int gasireParinte(int x)
    {
        int xx = x;

        while(x != parinte[x])
        {
            x = parinte[x];
        }

        while(xx != parinte[xx])
        {
            parinte[xx] = x;

            xx = parinte[xx];
        }

        return x;
    }


public:
    PaduriDisjuncte()
    {
        for(int i = 0; i < 200005; i++)
        {
            adancime[i] = 0;
            parinte[i] = i;
        }
    }

    void unire(int x, int y)
    {
        int nrx1 = adancime[x];
        int nrx2 = adancime[y];

        if(nrx1 < nrx2)
        {
            parinte[gasireParinte(x)] = gasireParinte(y);
        }
        else if(nrx1 > nrx2)
        {
            parinte[gasireParinte(y)] = gasireParinte(x);
        }
        else
        {
            parinte[gasireParinte(x)] = gasireParinte(y);
            adancime[y]++;
        }
    }

    bool suntUnite(int x, int y)
    {
        if(gasireParinte(x) == gasireParinte(y))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}multime;

void citire()
{
    scanf("%d %d", &n, &m);

    int tmp1, tmp2, tmp3;

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &tmp1, &tmp2, &tmp3);

        vecini.push_back(make_tuple(tmp3, tmp1, tmp2));
    }
}

void solve()
{
    sort(vecini.begin(), vecini.end());

    vector<pair<int, int> > sol;

    int l = vecini.size();
    int costTotal = 0;

    for(int i = 0; i < l; i++)
    {
        int tmp1 = get<1>(vecini[i]);
        int tmp2 = get<2>(vecini[i]);

        if(multime.suntUnite(get<1>(vecini[i]), get<2>(vecini[i])) == false)
        {
            multime.unire(get<1>(vecini[i]), get<2>(vecini[i]));
            costTotal += get<0>(vecini[i]);

            sol.push_back(make_pair(get<1>(vecini[i]), get<2>(vecini[i])));
        }
    }

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

    for(int i = 0; i < sol.size(); i++)
    {
        printf("%d %d\n", sol[i].second, sol[i].first);
    }
}

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

    citire();
    solve();

    return 0;
}