#include<cstdio>
using namespace std;
#include<algorithm>
#define NMAX 400100
struct muchie {int x, y, c;};
muchie v[NMAX];
int n, m, cost, comp[NMAX], nod1[NMAX], nod2[NMAX], k;
inline void cit(),reuniune(int,int); bool compar (muchie, muchie); int sel(int);
int main()
{freopen("apm.in","rt",stdin); freopen("apm.out","wt",stdout); 
 cit();
 for(int i=1;i<=n;i++) comp[i]=i;
 sort(v+1,v+m+1,compar);
 for(int i=1;i<=m;i++)
    if(sel(v[i].x)!=sel(v[i].y))
	   {cost+=v[i].c;  nod1[++k]=v[i].x; nod2[k]=v[i].y;
	    reuniune(v[i].x, v[i].y);
	   }
 printf("%d\n%d\n",cost,n-1);
 for(int i=1;i<=n-1;i++) printf("%d %d\n",nod1[i],nod2[i]);
 return 0;
}
inline void cit()
{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);
}
bool compar (muchie i, muchie j){return (i.c < j.c);}
int sel(int t)
{if (comp[t] == t) return t;
 comp[t]=sel(comp[t]); return comp[t];
}
inline void reuniune(int i, int j)
{comp[sel(i)] = sel(j);}