//#include <cstdio>
//#include <algorithm>
//using namespace std;
//const int NMAX=200005;
//const int MMAX=400005;
//struct KRUSK
//{
//    int x;
//    int y;
//    int c;
//};
//KRUSK a[MMAX];
//bool cmp(KRUSK a,KRUSK b)
//{
//    return a.c<b.c;
//}
//int t[NMAX];
//int h[NMAX];
//int x1[NMAX];
//int y1[NMAX];
//int FindSet(int x)
//{
//    while(t[x]!=x)
//        x=t[x];
//    return x;
//}
//void UnionSet(int x,int y)
//{
//    if(h[x]==h[y])
//    {
//        t[y]=x;
//        h[x]++;
//    }
//    else
//        if(h[x]>h[y])
//            t[y]=x;
//        else
//            t[x]=y;
//}
//int main()
//{
//    freopen("apm.in","r",stdin);
//    freopen("apm.out","w",stdout);
//    int n,m,i,s=0,nr=0,n1,n2,n3;
//    scanf("%d%d",&n,&m);
//    for(i=1;i<=n;i++)
//    {
//        t[i]=i;
//        h[i]=1;
//    }
//    for(i=1;i<=m;i++)
//    {
//        scanf("%d%d%d",&n1,&n2,&n3);
//        a[i].x=n1;
//        a[i].y=n2;
//        a[i].c=n3;
//    }
//    sort(a+1,a+m+1,cmp);
//    for(i=1;i<=m;i++)
//    {
//        if(FindSet(a[i].x)!=FindSet(a[i].y))
//        {
//            nr++;
//            s+=a[i].c;
//            x1[nr]=a[i].x;
//            y1[nr]=a[i].y;
//            UnionSet(FindSet(a[i].x),FindSet(a[i].y));
//            if(nr==n-1)
//                break;
//        }
//    }
//    printf("%d\n%d\n",s,nr);
//    for(i=1;i<=nr;i++)
//        printf("%d %d\n",x1[i],y1[i]);
//    return 0;
//}
#include <cstdio>
#include <algorithm>
using namespace std;
struct alpha
{
  int x,y,z;
};
alpha k[400005];
int t[200001],h[200001],n,m,i,u,v;
int findset(int x)
{
  while(t[x]!=x)
  x=t[x];
  return x;
}
void unionset(int x,int y)
{
    if(h[x]==h[y])
    t[y]=x,h[x]++;
    else
    if(h[x]>h[y])
    t[y]=x;
    else
    t[x]=y;
}
bool fs(alpha a,alpha b)
{
  return a.z<b.z;
}
int tet[200001],tet1[200001];
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=0;i<=200000;i++)
    {
      h[i]=1;t[i]=i;
    }
    for(i=1;i<=m;i++)
    {
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      k[i].x=a,k[i].y=b,k[i].z=c;
    }
    sort(k+1,k+m+1,fs);
    int sum=0;
    int cnt=0;
    for(i=1;i<=m;i++)
    {
      int tx=findset(k[i].x),ty=findset(k[i].y);
      if(tx!=ty)
      {unionset(tx,ty);sum+=k[i].z;cnt++;
      tet[cnt]=k[i].x;
      tet1[cnt]=k[i].y;
      }

    }
    printf("%d\n",sum);
    printf("%d\n",cnt);
    for(i=1;i<=cnt;i++)printf("%d %d\n",tet1[i],tet[i]);
    return 0;
}