#include <iostream>
#include <fstream>

using namespace std;

struct lista;

struct elem
{
    int a,b,c;
    bool apm;
    elem *urm;
    elem()
    {
        a=b=c=0;
        apm=0;
        urm=NULL;
    }
    ~elem()
    {
        if(urm!=NULL)
            delete urm;
    }
    friend lista;
};

struct lista
{
    elem *urm,*u;
    lista()
    {
        urm=NULL;
        u=NULL;
    }
    ~lista()
    {
        if(urm!=NULL)
            delete urm;
    }
};

struct lista2;

struct elem2
{
    int info;
    elem2 *urm;
    elem2()
    {
        info=-1;
        urm=NULL;
    }
    ~elem2()
    {
        if(urm!=NULL)
            delete urm;
    }
    friend lista2;
};

struct lista2
{
    elem2 *urm,*u;
    lista2()
    {
        urm=NULL;
        u=NULL;
    }
    ~lista2()
    {
        if(urm!=NULL)
            delete urm;
    }
    const int operator[](int x) const
    {
        int i;
        elem2 *p=urm;
        for(i=1;i<x;i++)
            p=p->urm;

        return p->info;
    }
    int& operator[](int x)
    {
        int i;
        elem2 *p=urm;
        for(i=1;i<x;i++)
            p=p->urm;
        return p->info;
    }
};

void kruskal(int n,int m,lista &l,lista2 &p)
{
    int i,x,y,nr=0;
/*    for(i=0;i<m-1;i++)
        for(j=i+1;j<m;j++)
            if(v[i]->c>v[j]->c)
                swap(v[i],v[j]);*/
    elem *pi,*qi;
    pi=l.urm;
    while(pi!=NULL&&pi->urm!=NULL)
    {
        qi=pi->urm;
        while(qi!=NULL)
        {
            if(pi->c>qi->c)
            {
                swap(pi->a,qi->a);
                swap(pi->b,qi->b);
                swap(pi->c,qi->c);
            }
            else
                qi=qi->urm;
        }
        pi=pi->urm;
    }
/*    for(i=0;i<m-1;i++)
        for(j=i+1;j<m;j++)
            if(v[i]->c==v[j]->c)
            {
                if(v[i]->a>v[j]->a)
                    swap(v[i],v[j]);
                else
                    if(v[i]->a==v[j]->a&&v[i]->b>v[j]->b)
                        swap(v[i],v[j]);
            }*/
    while(pi!=NULL&&pi->urm!=NULL)
    {
        qi=pi->urm;
        while(qi!=NULL)
        {
            if(pi->c==qi->c)
            {
                if(pi->a>qi->a)
                {
                    swap(pi->a,qi->a);
                    swap(pi->b,qi->b);
                    swap(pi->c,qi->c);
                }
                else
                    if(pi->a==qi->a&&pi->b>qi->b)
                    {
                        swap(pi->a,qi->a);
                        swap(pi->b,qi->b);
                        swap(pi->c,qi->c);
                    }
            }
            else
                qi=qi->urm;
        }
        pi=pi->urm;
    }
    elem2 *pi2;
    for(i=1;i<=n&&nr<=n-1;i++)
    {
        if(p.u==NULL)
        {
            pi2=new elem2;
            p.urm=pi2;
            p.u=pi2;
        }
        else
        {
            pi2=new elem2;
            p.u->urm=pi2;
            p.u=pi2;
        }
    }
    for(pi=l.urm;pi!=NULL;pi=pi->urm)
    {
        x=pi->a;
        y=pi->b;
        if(p[x]==p[y])
        {
            if(p[x]<=-1)
            {
                p[y]+=p[x];
                p[x]=y;
                nr++;
                pi->apm=1;
            }
        }
        else
        {
            if(p[x]<=-1&&p[y]<p[x])
            {
                p[y]+=p[x];
                p[x]=y;
                nr++;
                pi->apm=1;
            }
            else
            {
                if(p[y]<=-1&&p[x]<p[y])
                {
                    p[x]+=p[y];
                    p[y]=x;
                    nr++;
                    pi->apm=1;
                }
                else
                {
                    int e=x,f=y;
                    while(p[e]>-1)
                        e=p[e];
                    while(p[f]>-1)
                        f=p[f];
                    if(e==f)
                        continue;
                    if(p[e]==p[f])
                    {
                        p[f]+=p[e];
                        p[e]=f;
                        nr++;
                        pi->apm=1;
                    }
                    else
                    {
                        if(p[f]<p[e])
                        {
                            p[f]+=p[e];
                            p[e]=f;
                            nr++;
                            pi->apm=1;
                        }
                        else
                        {
                            p[e]+=p[f];
                            p[f]=e;
                            nr++;
                            pi->apm=1;
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    int n,m,i,nr=0;
    lista l;
    lista2 p;
    ifstream f("apm.in");
    f>>n>>m;
    for(i=0;i<m;i++)
    {
        int x,y,z;
        elem *p;
        f>>x>>y>>z;
        p=new elem;
        p->a=x;
        p->b=y;
        p->c=z;
        if(l.u==NULL)
        {
            l.urm=p;
            l.u=p;
        }
        else
        {
            l.u->urm=p;
            l.u=p;
        }
    }
    f.close();
    kruskal(n,m,l,p);
    ofstream g("apm.out");
    for(elem *pi=l.urm;pi!=NULL;pi=pi->urm)
        if(pi->apm==1)
            nr+=pi->c;
    g<<nr<<endl<<n-1<<endl;
    for(elem *pi=l.urm;pi!=NULL;pi=pi->urm)
        if(pi->apm==1)
            g<<pi->a<<" "<<pi->b<<endl;
    g.close();
    return 0;
}