#include <fstream>
using namespace std;
ifstream  fin("apm.in");
ofstream fout("apm.out");
struct nod2{
    int vecin,cost;
    nod2 *leg;
};
nod2 *LV[200005], *p;
int n, m, d[200005], heap[200005], nh, infinit=1000000000, tata[200005], poz[200005];
char viz[200005];

void urcare(int p){
    int y=heap[p];///nodul
    int x=d[y];///valoarea
    while(p/2>=1 && d[heap[p/2]]>x){
        heap[p]=heap[p/2];
        poz[heap[p/2]]=p;
        p=p/2;
    }
    heap[p]=y;
    poz[y]=p;
}

void coborare(int p){
    int y=heap[p];///nodul
    int x=d[y];///valoarea
    int r;
    while(p*2<=nh){
        r=p*2;
        if(r+1<=n && d[heap[r+1]]<d[heap[r]]){
            r++;
        }
        if(d[heap[r]]<x){
            heap[p]=heap[r];
            poz[heap[r]]=p;
            p=r;
        }
        else{
            break;
        }
    }
    heap[p]=y;
    poz[y]=p;
}

int main()
{
    int i,u,v,c,jmin,smin;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>u>>v>>c;
        p=new nod2;
        p->vecin=v;
        p->cost=c;
        p->leg=LV[u];
        LV[u]=p;

        p=new nod2;
        p->vecin=u;
        p->cost=c;
        p->leg=LV[v];
        LV[v]=p;
    }
    for(i=1;i<=n;i++){
        d[i]=infinit;
        tata[i]=-1;
        viz[i]=0;
    }
    tata[1]=0;
    d[1]=0;

    heap[1]=1;
    poz[1]=1;
    nh=1;

    for(i=2;i<=n;i++){
        nh++;
        heap[nh]=i;
        poz[i]=nh;
        urcare(nh);
    }

    smin=0;
    for(i=1;i<=n;i++){
        jmin=heap[1];
        smin=smin+d[jmin];
        viz[jmin]=1;
        ///sterg primul din heap
        heap[1]=heap[nh];
        poz[heap[nh]]=1;
        nh--;
        coborare(1);
        ///caut imbunatatiri
        for(p=LV[jmin];p;p=p->leg){
            if(viz[p->vecin]==0 && d[p->vecin]>p->cost){
                d[p->vecin]=p->cost;
                tata[p->vecin]=jmin;
                urcare(poz[p->vecin]);
            }
        }
    }
    fout<<smin<<"\n";
    fout<<n-1<<"\n";
    for(i=2;i<=n;i++){
        fout<<i<<" "<<tata[i]<<"\n";
    }
    fout.close();
    fin.close();
    return 0;
}