#include <fstream>
#include <vector>
#include <algorithm>

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

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

int N,M,RG[NMAX],TT[NMAX],X[MMAX],Y[MMAX],C[MMAX],IND[MMAX],ANS,x,y,cont;
vector <int> vans;

bool cmp(int a, int b)
{
    return (C[a] < C[b]);
}

int find(int nod)
{
    int R = nod,y;
    for (; R != TT[R]; R = TT[R]);

    for (; nod != TT[nod];)
    {
        y = TT[nod];
        TT[nod] = R;
        nod = 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[i] >> Y[i] >> C[i];
        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))
        {
            ANS += C[ IND[i] ];
            cont++;
            vans.push_back(IND[i]);
            unite(find(x),find(y));
        }
    }

    g << ANS << '\n';
    g << cont << '\n';

    for (int i = 0; i < N-1; ++i)
    {
        g << X[ vans[i] ] << " " << Y[ vans[i] ] << '\n';
    }

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