#include <cstdio>
#include <algorithm>
using namespace std;
int t[100005],h[100005];
struct ad
{
  int x,y,z;
};
ad v[100005];
bool cmp(ad a,ad b)
{
  if(a.z==b.z)
    {
      return 1;
}
else
  return a.z<b.z;
};
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[x]=y;
    if(h[x]>h[y])
      t[y]=x;
    if(h[x]==h[y])
    {
      t[y]=x;
      h[x]++;
    }
}
bool a[100005];
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n , r;
    scanf("%d%d",&n,&r);
    for(int i=1;i<=r;i++)scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].z);
    sort(v+1,v+r+1,cmp);
    for(int i=1;i<=n;i++)t[i]=i,h[i]=1;
    int cost=0,cnt=0;
    for(int i=1;i<=r;i++)
      {
        if(cnt==n-1)break;
        int l=findset(v[i].x),l1=findset(v[i].y);
        if(l!=l1)
        {
          unionset(l,l1);
          cnt++;
          cost+=v[i].z;
          a[i]=1;
        }
      }
      printf("%d\n",cost);
      printf("%d\n",n-1);
      for(int i=1;i<=r;i++)
        if(a[i])printf("%d %d\n",v[i].x,v[i].y);
    return 0;
}