#include<fstream>
using namespace std;
int n,m,i,k,x,y,val,viz[200002],s,poz,cost1[200002],tata[200002],dmin;
struct nod
{
    int x,cost;
    nod *leg;
};
nod *p,*v[200002];
int main()
{
     ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>val;
        p=new nod;
        p->x=y;
        p->cost=val;
        p->leg=v[x];
        v[x]=p;
        p=new nod;
        p->x=x;
        p->cost=val;
        p->leg=v[y];
        v[y]=p;
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
        cost1[i]=2000000;
        tata[i]=-1;
    }
    cost1[1]=0;
    tata[1]=0;
    for(k=1;k<=n-1;k++)
    {
        dmin=2000000;
        for(i=1;i<=n;i++)
        {
            if(cost1[i]<dmin && viz[i]==0)
            {
                dmin=cost1[i];
                poz=i;
            }
        }
        viz[poz]=1;
        for(p=v[poz];p!=0;p=p->leg)
        {
            if(viz[p->x]==0 && p->cost<cost1[p->x])
            {
                cost1[p->x]=p->cost;
                tata[p->x]=poz;
            }
        }
    }
    s=0;
    for(i=1;i<=n;i++)
    {
        s=s+cost1[i];
    }
    fout<<s<<"\n";
    fout<<n-1<<"\n";
    for(i=2;i<=n;i++)
    {
        fout<<i<<" "<<tata[i]<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}