#include <stdio.h>
#include <algorithm>
#define mm 400001

using namespace std;

struct s{int x,y,c;};

int i,j,n,m,x,y,z,apm,apn;
bool o,a[mm],b[mm];
s v[mm],M[mm];

bool cmp(s i,s j)
{
    return(i.c<j.c);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
     scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    stable_sort(v+1,v+m+1,cmp);
    b[v[1].x]=1; j=2;
    for(i=1;i<=m;i++)
     if(!a[i])
         if((b[v[i].x]&&!b[v[i].y])||(!b[v[i].x]&&b[v[i].y]))
          {a[i]=1;b[v[i].x]=1; b[v[i].y]=1;o=0;apm+=v[i].c; M[++apn]=v[i];i=j-1;}
     else if(!o) {o=1; j=i;}
    printf("%d\n%d\n",apm,apn);
    for(i=1;i<=apn;i++)
     printf("%d %d\n",M[i].x,M[i].y);
    return 0;
}