#include <fstream>
#include <algorithm>

const int NMAX = 200005;
const int MMAX = 400005;

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int N,M,X[MMAX],Y[MMAX],C[MMAX],IND[MMAX],RG[NMAX],TT[NMAX],x,y,z,ans,cont,I,SOL[MMAX];

bool cmp(int i, int j)
{
    return (C[i] < C[j]);
}

int find(int x)
{
    int R = x, y;

    for (; TT[R] != R; R = TT[R]);

    for (; TT[x] != x;)
    {
        y = TT[x];
        TT[x] = R;
        x = y;
    }

    return R;
}

void unite(int x, int y)
{
    if (RG[x] > RG[y])
    {
        TT[y] = x;
    }
    else TT[x] = y;

    if(RG[x] == RG[y])
        RG[y]++;
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        f >> x >> y >> z;
        X[i] = x;
        Y[i] = y;
        C[i] = z;
        IND[i] = i;
    }

    sort(IND+1, IND+M+1, cmp);

    for (int i = 1; i <= N; ++i)
    {
        RG[i] = 1;
        TT[i] = i;
    }

    for (int i = 1; i <= M; ++i)
    {
        x = X[ IND[i] ];
        y = Y[ IND[i] ];
        if(find(x) != find(y))
        {
            unite(find(x),find(y));
            ans += C[ IND[i] ];
            cont++;
            SOL[cont] = IND[i];
        }
    }

    g << ans << '\n';
    g << cont << '\n';
    for (int i = 1; i <= cont; ++i)
    {
        I = SOL[i];
        g << X[I] << " " << Y[I] << '\n';
    }

    f.close();
    g.close();
    return 0;
}