#include<fstream>
using namespace std;
ifstream  fin("apm.in");
ofstream fout("apm.out");
struct nod2
{
    int vecin,cost;
    nod2 *leg;
};

nod2 *LV[200002], *p;
int N,M,d[200002], coada[200002], pr, ul, nrcoada, i, x, y, c, T[200002];
char viz[200002];
int main()
{
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        p=new nod2;
        p->vecin=y;
        p->cost=c+1000;
        p->leg=LV[x];
        LV[x]=p;
        p=new nod2;
        p->vecin=x;
        p->cost=c+1000;
        p->leg=LV[y];
        LV[y]=p;
    }
    for(i=1;i<=N;i++)
    {
        d[i]=1000000000;
        viz[i]=0;
        T[i]=-1;
    }
    T[1]=0;
    d[1]=0;
    coada[1]=1;
    pr=1;
    ul=1;
    nrcoada=1;
    viz[1]=1;
    while(nrcoada>0)
    {
        x=coada[pr];
        for(p=LV[x];p;p=p->leg)
        {
            y=p->vecin;
            c=p->cost;
            if(c<d[y])
            {
                d[y]=c;
                T[y]=x;
                if(viz[y]==0)
                {
                    viz[y]=1;
                    ul++;
                    if(ul>N)
                    {
                        ul=1;
                    }
                    coada[ul]=y;
                    nrcoada++;
                }
            }
        }
        viz[x]=0;
        pr++;
        if(pr>N)
        {
            pr=1;
        }
        nrcoada--;
    }
    int s=0;
    for(i=2;i<=N;i++)
    {
        s=s+d[i]-1000;
    }
    fout<<s<<"\n";
    fout<<N-1<<"\n";
    for(i=2;i<=N;i++)
    {
        fout<<i<<" "<<T[i];
        //<<" "<<d[i]-1000
        fout<<"\n";
    }
    fout.close();
    fin.close();
    return 0;
}