#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");

struct muchie {
    int a,b,cost;
} v[400005];
bool vizitat[200005], muchie_in_apcm[400005];
int tata[200005];

bool cond (muchie x, muchie y)
{
    if (x.cost>y.cost)
        return false;
    return true;
}

int main ()
{
    int n,m,i,a,b;
    cin>>n>>m;
    for (i=1;i<=m;++i)
        cin>>v[i].a>>v[i].b>>v[i].cost;
    cin.close();

    for (i=1;i<=n;++i)
        tata[i]=i;
    sort (v+1,v+m+1,cond);

    bool OK;
    int nr_muchii=0,cost_total=0,muchie_curenta=0;
    do {
        OK=true;
        muchie_curenta++;
        if (!vizitat[v[muchie_curenta].a]||!vizitat[v[muchie_curenta].b])
        {
            a=v[muchie_curenta].a,b=v[muchie_curenta].b;
            nr_muchii++;
            cost_total=cost_total+v[muchie_curenta].cost;
            vizitat[a]=true;
            vizitat[b]=true;
            muchie_in_apcm[muchie_curenta]=true;

            if (tata[a]<tata[b])
            {
                for (i=1;i<=n&&i!=b;++i)
                    if (tata[i]==tata[b])
                        tata[i]=tata[a];
                tata[b]=tata[a];
            }
            else
            {
                for (i=1;i<=n&&i!=a;++i)
                    if (tata[i]==tata[a])
                        tata[i]=tata[b];
                tata[a]=tata[b];
            }
        }
        for (i=1;i<=n&&OK;++i)
            if (!vizitat[i])
                OK=false;
    }while (!OK);

    OK=false;
    for (i=1;i<=m&&!OK;++i)
        if (!muchie_in_apcm[i]&&tata[v[i].a]!=tata[v[i].b])
            nr_muchii++,cost_total=cost_total+v[i].cost,muchie_in_apcm[i]=true,OK=true;

    cout<<cost_total<<endl<<nr_muchii<<endl;
    for (i=1;i<=m;++i)
        if (muchie_in_apcm[i])
            cout<<v[i].a<<' '<<v[i].b<<endl;
    cout.close();
    return 0;
}