# include <fstream>
# include <vector>
# define DIM 200010
# define INF 1000000000
# define f first
# define s second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector <pair<int,int> > Lista[DIM];
pair <int,int> h[DIM],d[DIM],sol[DIM];
int val[DIM],n,m,i,j,t,x,y,cost,k,nr,nc,nv;
void add(int poz){
    t++;
    d[poz].s=t;
    h[t].f=d[poz].f;
    h[t].s=poz;
    int c=t,p=t/2;
    while(p!=0){
        if(h[c].f<h[p].f){
            swap(h[c],h[p]);
            d[h[c].s].s=c;
            d[h[p].s].s=p;
            c=p;
            p/=2;
        }
        else
            break;
    }
}
void change(int poz){
    int poz1=h[poz].s;
    h[poz].f=d[poz1].f;
    int c=poz,p=poz/2;
    while(p!=0){
        if(h[c].f<h[p].f){
            swap(h[c],h[p]);
            d[h[c].s].s=c;
            d[h[p].s].s=p;
            c=p;
            p/=2;
        }
        else
            break;
    }
}
void off(){
    d[h[1].s].f=-INF;
    h[1]=h[t--];
    d[h[1].s].s=1;
    int p=1,c=2;
    while(c<=t){
        if(h[c+1].f<h[c].f&&c+1<=t)
            c++;
        if(h[c].f<h[p].f){
            swap(h[c],h[p]);
            d[h[c].s].s=c;
            d[h[p].s].s=p;
            p=c;
            c*=2;
        }
        else
            break;
    }
}
int main () {
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        Lista[x].push_back(make_pair(y,cost));
        Lista[y].push_back(make_pair(x,cost));
    }
    add(1);
    for(i=2;i<=n;i++){
        d[i].f=INF;
        add(i);
    }
    for(i=1;i<=n;i++){
        nc=h[1].s;
        //fout<<nc<<"\n";
        if(i>1){
            nr+=h[1].f;
            sol[++k].f=nc;
            sol[k].s=val[nc];
        }
        off();
        for(j=0;j<Lista[nc].size();j++){
            nv=Lista[nc][j].f;
            cost=Lista[nc][j].s;
            if(d[nv].f>=cost){
                d[nv].f=cost;
                val[nv]=nc;
                change(d[nv].s);
            }
        }
    }
    fout<<nr<<"\n"<<n-1<<"\n";
    for(i=1;i<=k;i++)
        fout<<sol[i].f<<" "<<sol[i].s<<"\n";
    return 0;
}