#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchii
{
    int x;
    int y;
    short z;
    int luat;
};
muchii L[400001];
int cmp(muchii a,muchii b)
{
    return a.z<b.z;
}
int cc[200001],n,m,cost;
int main()
{
    int i,j,xi,yi;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>L[i].x>>L[i].y>>L[i].z;
        /* for(j=1;j<i;j++)
              if(L[j].x==L[i].x&&L[j].y==L[i].y)
                  if(L[i].z>L[j].z)
                 { i--;m--;}
                  else
                      {L[j].z=L[i].z;i--;m--;}*/
    }
    sort(L+1,L+m+1,cmp);
    for(i=1;i<=n;i++)cc[i]=i;
     
    for(i=1;i<=m;i++)
    {
        xi=L[i].x;
        yi=L[i].y;
        if(cc[xi]!=cc[yi])
        {
            cost+=L[i].z;
            L[i].luat=1;
			int val1,val2;
			val1=cc[xi];
			val2=cc[yi];
            for(j=1;j<=n;j++)
                if(cc[j]==val1)cc[j]=val2;
             
             
        }
         
    }
    g<<cost<<"\n"<<n-1<<'\n';
    for(i=1;i<=m;i++)
        if(L[i].luat)g<<L[i].x<<" "<<L[i].y<<'\n';
    /*for(i=1;i<=m;i++)
        g<<L[i].z<<" ";
    g<<'\n';
    for(i=1;i<=m;i++)
        g<<L[i].luat<<" ";
    g<<'\n';
    for(i=1;i<=n;i++)
        g<<cc[i]<<" ";
    g<<n<<"<-";*/
    return 0;
}