#include <fstream>
#include <algorithm>

using namespace std;

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

struct muchie
{
    int x,y,c;
};

muchie v[400020];
bool c[400020];

int rx,ry,N,M,cost,t[200020];

bool cmp (muchie a, muchie b)
{
    return a.c<b.c;
}

int radacina (int x)
{
    if (t[x] == 0) return x;
    int r = radacina (t[x]);
    t[x] = r;
    return r;
}

int kruskal ()
{
    sort (v+1,v+M+1,cmp);
    int cost = 0;
    int nr = 0;
    for (int i=1 ; i<=M ; i++)
    {
        rx = radacina(v[i].x);
        ry = radacina(v[i].y);
        if (rx == ry) continue;
        nr++;
        c[i] = true;
        cost += v[i].c;
        t[ry] = rx;
        if (nr == N-1) break;
    }
}

int main()
{
    in>>N>>M;
    for (int i=1 ; i<=M ; i++)
    {
        in>>v[i].x>>v[i].y>>v[i].c;
    }
    kruskal();
    out<<cost<<"\n"<<N-1<<"\n";
    for (int i=1 ; i<=M ; i++)
    {
        if (c[i] == true)
            out<<v[i].x<<" "<<v[i].y<<"\n";
    }
    return 0;
}