# include <fstream>
# include <vector>
# include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x, y, cost;
}a[400005];
bool cmp (muchie x, muchie y)
{
    if (x.cost>=y.cost) return 0;
       else return 1;
}
int i,j,n,m,x,y,VV,luate,costfinal;
int R[200005],marime[200005],sol[200005];
int radacina (int x)
{
    while (x!=R[x])
        x=R[x];
    return x;
}
void APM ()
{
    int i,Rx,Ry;
    for (i=1; i<=m; ++i)
    {
        Rx=radacina(a[i].x);
        Ry=radacina(a[i].y);
        if (VV==n-1)
        {
            VV+=0;
        }
        if (Rx!=Ry)
        {
            costfinal+=a[i].cost; sol[++VV]=i;
            if (marime[Rx]>marime[Ry]) R[a[i].y]=Rx, marime[Rx]+=marime[Ry];
            else R[a[i].x]=Ry, marime[Ry]+=marime[Rx];
        }
    }
}
int main ()
{
    f>>n>>m;
    for (i=1; i<=m; ++i)
    {
        if (i<=n) R[i]=i, marime[i]=1;
        f>>a[i].x>>a[i].y>>a[i].cost;
    }
    sort (a+1,a+m+1,cmp);
    APM ();
    g<<costfinal<<"\n"<<VV<<"\n";
    for (i=1; i<=VV; ++i)
        g<<a[sol[i]].x<<" "<<a[sol[i]].y<<"\n";
    return 0;
}