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

const int NMAX = 200015;

using namespace std;

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

struct muchie
{
    int a,b,c;

    bool operator < (const muchie &t) const
    {
        if (t.c > c)
            return true;
        return false;
    }
};

muchie v[NMAX];
int N,M,cost;
int TT[NMAX];
vector < pair<int,int> > sol;

int Query(int nod)
{
    if (TT[nod] == nod)
        return nod;
    TT[nod] = Query(TT[nod]);
    return TT[nod];
}

void Update(int x, int y)
{
    if (x > y)
        swap(x,y);
    TT[x] = y;
}

int main()
{
    f >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        f >> v[i].a >> v[i].b >> v[i].c;
    }

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

    sort(v+1,v+M+1);

    for (int i = 1; i <= M; ++i)
    {
        int q1 = Query(v[i].a);
        int q2 = Query(v[i].b);

        if (q1 != q2)
        {
            Update(q1,q2);
            cost += v[i].c;
            sol.push_back(make_pair(v[i].a,v[i].b));
        }
    }

    g << cost << '\n';
    g << sol.size() << '\n';
    for (int i = 0; i < sol.size(); ++i)
    {
        g << sol[i].first << " " << sol[i].second << '\n';
    }

    f.close();
    g.close();

    return 0;
}