#include <fstream>
#include<vector>

using namespace std;
#define Nmax 200005
#define oo (1<<30)
ifstream fin("apm.in");
ofstream fout("apm.out");
int nr,h[Nmax],n,m,cost;
int d[Nmax], tata[Nmax];
bool viz[Nmax];
struct elem{
    int x,c;
};
vector <elem> v[Nmax];
void down(int k){
    int f;
   while(2*k<=nr){
        f=2*k;
        if(2*k+1<=nr && d[h[f]]>d[h[2*k+1]])
               f=2*k+1;
        if(d[h[k]]>d[h[f]])
            {swap(h[k],h[f]);k=f;}
        else return;
        }
}
void up(int k){

   while(k/2>0 && d[h[k]]<d[h[k/2]]){
        swap(h[k],h[k/2]);
        k=k/2;
   }
}
void heap(){
for(int i=1;i<=nr;i++)
    fout<<h[i]<<" ";
fout<<"\n";
}
elem make_elem(int x,int c){
    elem z;
    z.x=x;z.c=c;
    return z;
}
void cit(){
    fin>>n>>m;
    int x,y,c;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[x].push_back(make_elem(y,c));
        v[y].push_back(make_elem(x,c));
    }
}
;
int main(){
    int x,y,c;
   cit();

   for(int i=1;i<=n;i++)
    d[i]=oo;
    d[1]=0;tata[1]=0; viz[1]=1;
    for(unsigned int i=0;i<v[1].size();i++)
    {
        x=v[1][i].x;c=v[1][i].c;
        d[x]=c; tata[x]=1;
        h[++nr]=x;
        up(nr);
    }

    for(int k=1;k<=n-1;k++){
        x=h[1];
        h[1]=h[nr];
        nr--;
        down(1);
        viz[x]=1;
        for(unsigned int i=0;i<v[x].size();i++){
            y=v[x][i].x;c=v[x][i].c;
            if(!viz[y] && d[y]>c)
            {
                d[y]=c; tata[y]=x;
                h[++nr]=y;
                up(nr);

            }
        }
    }
    for(int i=1;i<=n;i++) cost+=d[i];
    fout<<cost<<"\n";
    fout<<n-1<<"\n";
    for(int i=2;i<=n;i++)
        fout<<i<<" "<<tata[i]<<"\n";
    return 0;
}