#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=9999;
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>inf)
    {
        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;
    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=0;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();
}