#include<cstdio>
#include<algorithm>

const int NMAX=400000;

bool marc[NMAX+1];

struct date
{
 int x,y,c;
};
date v[NMAX+1];

int ad[NMAX+1];//adancime
int master[NMAX+1];//tata//master

bool comp(date a,date b)
{
 if(a.c<b.c)
    return true;
 return false;
}

int main()
{
 freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout);
 int n,m;
 scanf("%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
    {
     scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].c);
     master[v[i].x]=v[i].x;
     master[v[i].y]=v[i].y;
     ad[v[i].x]=ad[v[i].y]=1;
    }
 std::sort(v+1,v+m+1,comp);
 int rez=0,nr=0;
 for(int i=1;i<=m;i++)
    {
     int rad1=v[i].x,rad2=v[i].y;
     while(master[rad1]!=rad1)
           rad1=master[rad1];
     while(master[rad2]!=rad2)
           rad2=master[rad2];
     if(rad1!=rad2)
        {
         if(ad[rad1]<=ad[rad2])
            {
             master[rad2]=master[rad1];
             master[v[i].y]=master[rad1];
             ad[v[i].y]+=ad[v[i].x];
             rez+=v[i].c;
             nr++;
             marc[i]=true;
            }
         else
            {
             if(ad[rad1]>ad[rad2])
                {
                 master[rad1]=master[rad2];
                 master[v[i].x]=master[rad2];
                 ad[v[i].x]+=ad[v[i].y];
                 rez+=v[i].c;
                 nr++;
                 marc[i]=true;
                }
            }
        }
    }
 printf("%d\n%d\n",rez,nr);
 for(int i=1;i<=m;i++)
    {
     if(marc[i]==true)
        printf("%d %d\n",v[i].x,v[i].y);
    }
return 0;
}