#include <cstdio>
#include <algorithm>
using namespace std;
struct alpha
{
  int x,y,z;
};
alpha k[265];
int t[265],h[265],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[265],tet1[265];
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=0;i<=256;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;
}