#include <fstream>
#include<algorithm>
using namespace std;
#define inf 1e9-1
#define N 200200
#define s second
#define f first
#define mp make_pair
ifstream f("apm.in");
ofstream G("apm.out");int S,I;const int D=59999;char p[D+1],w[D+2];inline void R(int&x){x=0;S=1;while(p[I]<40)if(++I>D)I=0,f.read(p,D+1);if(p[I]<47){S=-1;if(++I>D)I=0,f.read(p,D+1);}while(p[I]>47){x=x*10+p[I]-48;if(++I>D)I=0,f.read(p,D+1);}x*=S;}int t[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};inline void W(int x){if(x>t[9]-1){w[I]='\n';if(++I>D)I=0,G<<w;return;}if(x<0){w[I]='-';if(++I>D)I=0,G<<w;x*=-1;}int c,i;if(x>t[3]-1)for(i=4;x>t[i]-1;++i);else for(i=0;x>t[i]-1;++i);--i;for(;i>-1;--i){c=x/t[i],x-=c*t[i],w[I]=48+c;if(++I>D)I=0,G<<w;}w[I]=' ';if(++I>D)I=0,G<<w;}inline void T(){w[I]=0;G<<w;}int x,y,z,n,m,j,l,g[N],A,o=-1,h[N],s[2*N];pair<int,pair<int,int> >v[2*N];int main(){R(n);R(m);for(;j<m;++j)R(v[j].s.f),R(v[j].s.s),R(v[j].f);sort(v,v+m);++n;for(j=1;j<n;++j)h[j]=1,g[j]=j;--n;for(j=0;h[1]<n;++j){x=v[j].s.f;y=v[j].s.s;while(x>g[x])z=g[g[x]],g[x]=z,x=z;while(y>g[y])z=g[g[y]],g[y]=z,y=z;if(x!=y){s[++o]=j;A+=v[j].f;if(x>y)h[y]+=h[x],h[x]=0,g[x]=y;else h[x]+=h[y],h[y]=0,g[y]=x;}}I=0;W(A);W(t[9]);W(++o);W(t[9]);for(j=0;j<o;++j)W(v[s[j]].s.f),W(v[s[j]].s.s),W(t[9]);T();}