#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int m,n,S,i,k,Nr=1;
int x,y,c;
int v[200006];
int Dm[200000],Dad[200000];
int F[200000][2];
int h[200000],l[200000];
//arbore binar, unde n tata pt 2n si 2n+1, deci n fiu la [n/2]
struct muchie{int b,c;muchie *n;} *a[200000],*p;
void replac()
{
    while((2*i<Nr && v[h[i]]>v[h[2*i]])||(2*i+1<Nr && v[h[i]]>v[h[2*i+1]]))
    {
        if(i*2+1>Nr||v[h[2*i]]<v[h[2*i+1]])
        {
            swap(Dm[h[i]],Dm[h[i/2]]);
            swap(h[i],h[i/2]);
            i+=i;
        }
        else
        {
            swap(Dm[h[i]],Dm[h[i*2+1]]);
            swap(h[i],h[i*2+1]);
            i+=i+1;
        }
    }
}
void emuchie(int i)
{
    F[k][0]=i;
    F[k][1]=Dad[i];
    ++k;
}
void inn(int i)
{
    while(i>1 && Dm[h[i]]<Dm[h[i/2]])
    {
        swap(Dm[h[i]],Dm[h[i/2]]);
        swap(h[i],h[i/2]);
        i=i/2;
    }
}
void add(int i)
{
    h[Nr]=i;
    l[i]=Nr;
    inn(i);
    ++Nr;
}
void gn(int i)
{
    while(a[i]!=NULL)
    {
        if(Dm[a[i]->b]>a[i]->c)
        {
            Dm[a[i]->b]=a[i]->c;
            Dad[a[i]->b]=i;
            if(l[a[i]->b])inn(a[i]->b);
        }
        a[i]=a[i]->n;
    }
}
void gs()
{
    emuchie(h[0]);

}
int main()
{
    f>>n>>m;
    for(int i=0;i<m;++i){
            f>>x>>y>>c;
            p=new muchie;
            p->b=y;p->c=c;
            p->n=a[x];
            a[x]=p;
            p=new muchie;
            p->b=x;p->c=c;
            p->n=a[y];
            a[y]=p;
    }
    for(int i=1;i<=n;++i){Dm[i]=v[i]=200000200;}
    for(int i=1;i<=n;++i){add(i);}
    v[1]=0;
    ++k;
    gn(1);
    m=1;
    while(m!=n)
    {



        ++m;
    }
    /*for(i=1;i<m;++i)
    {
        if(v[a[i].a]!=v[a[i].b])
    {
        v[a[i].a]=v[a[i].b]=1;
        S+=a[i].c;
        i=0;
    }
    }*/
    g<<S<<'\n'<<n-1<<'\n';
    for(int i=1;i<k;++i)g<<F[i][0]<<' '<<F[i][1]<<'\n';
}