#include <algorithm>
#include <fstream>
using namespace std;

const int MAXN = 2e5 + 3, MAXM = 4e5 + 3;

class Padure
{
    int T[MAXN], d[MAXN];

    int radacina(int nod)
    {
        if ( nod == T[nod] )
            return nod;

        return T[nod] = radacina(T[nod]);
    }

public:

    Padure()
    {
        for (int i = 1; i < MAXN; ++i)
        {
            T[i] = i;
            d[i] = 1;
        }
    }

    bool merge(int x, int y)
    {
        x = radacina(x);
        y = radacina(y);
        if ( x == y )
            return false;

        if ( d[x] < d[y] ){
            T[x] = y;
            d[y] += d[x];
        } else {
            T[y] = x;
            d[x] += d[y];
        }
        return true;
    }

    bool query(int x, int y)
    {
        return radacina(x) == radacina(y);
    }
};

struct Muchie
{
    int x, y, c;

    inline bool operator< (const Muchie& m) const{
        return c < m.c;
    }
};

int N, M;
Muchie edge[MAXM];
Padure pmd;

void read()
{
    ifstream fin("apm.in");

    fin >> N >> M;
    for (int i = 0; i < M; ++i)
        fin >> edge[i].x >> edge[i].y >> edge[i].c;

    fin.close();
}

int APM()
{
    sort(edge, edge + M);

    int C = 0;
    for (int k = 0, i = 0; k < N-1; ++i)
        if ( pmd.merge(edge[i].x, edge[i].y) ){
            C += edge[i].c;
            edge[k++] = edge[i];
        }

    return C;
}

int main()
{
    read();

    ofstream fout("apm.out");
    fout << APM() << '\n' << N-1 << '\n';
    for (int i = 0; i < N - 1; ++i)
        fout << edge[i].x << ' ' << edge[i].y << '\n';

    fout.close();

    return 0;
}