#include <fstream>
#define pinf 1<<30
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct nod
{
  int info,c;
  nod *next;
};
nod *l[200001],*p;
int i,j,n,m,cost,no[400001],s,nr,rez[2][200001],w,lin,col,k,x,y,minn;
bool viz[200001];
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>cost;
        p=new nod;
        p->c=cost;
        p->info=y;
        p->next=l[x];
        l[x]=p;
        p=new nod;
        p->c=cost;
        p->next=l[y];
        p->info=x;
        l[y]=p;
    }
    viz[1]=1;
    no[++w]=1;
    while(w<n)
    {
        minn=pinf;
        for(i=1;i<=w;++i)
        {
            p=new nod;
            p=l[no[i]];
            while(p)
            {
                if(p->c<minn&&viz[no[i]]==1&&viz[p->info]==0)
                    {
                        minn=p->c;
                        lin=no[i];
                        col=p->info;
                    }
                p=p->next;
            }
        }
        s+=minn;
        rez[0][++k]=lin;
        rez[1][k]=col;
        viz[col]=1;
        no[++w]=col;
    }
    fout<<s<<'\n';
    fout<<k<<'\n';
    for(i=1;i<=k;++i)
        fout<<rez[0][i]<<" "<<rez[1][i]<<'\n';

    return 0;
}