#include<fstream>
using namespace std;
int t[20000],v[20000][20000];
long k,n,m,x[20000],y[20000];
void q(long e,long v)
{
    if(e<v)
    {
        k=t[(e+v)/2];
        long i,j;
        i=e-1;
        j=v+1;
        while(i<j)
        {
            do{
                i++;
            }while(t[i]<k);
            do{
                j--;
            }while(t[j]>k);
            if(i<j)
            {
                swap(t[i],t[j]);
                swap(x[i],x[j]);
                swap(y[i],y[j]);
            }
        }
        q(e,j);
        q(j+1,v);
    }
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    long i,j,h=0;
    int c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x[i]>>y[i]>>t[i];
        v[x[i]][y[i]]=t[i];
        v[y[i]][x[i]]=t[i];
    }
    q(1,m);
    h=0;
    k=m;
    long kov[10000],a,b;
    bool vo[10000];
    while(h!=m-n+1)
    {
        b=0;a=1;
        bool jo=0;
        for(i=1;i<=n;i++)
        {
            vo[i]=0;
            if(v[x[k]][i]!=0&&i!=y[k])
            {
                kov[++b]=i;
                vo[i]=1;
            }
        }
        vo[x[k]]=1;
        while(a<=b&&jo==0)
        {
            for(i=1;i<=n&&jo==0;i++)
            {
                if(v[kov[a]][i]!=0&&vo[i]==0)
                {
                    kov[++b]=i;
                    vo[i]=1;
                    if(i==y[k])
                        jo=1;
                }
            }
            a++;
        }
        if(jo)
        {
            v[x[k]][y[k]]=0;
            v[y[k]][x[k]]=0;
            h++;
        }
        k--;
    }
    h=0;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        h+=v[i][j];
    g<<h<<"\n"<<n-1<<"\n";
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        if(v[i][j]!=0)
        g<<i<<" "<<j<<"\n";
    f.close();
    g.close();
    return 0;
}