#include <cstdio>
#include <vector>

using namespace std;

FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");

struct tip{
    int x,c;
};

vector<tip> v[200001];

tip rec[200001];

int h[200001],d[200001],si,n,m,poz[200001],s;

inline void schimb(int i,int j){
    int aux=h[i];
    h[i]=h[j];
    h[j]=aux;
    poz[h[i]]=i;
    poz[h[j]]=j;
}

void up(int x){
    while ( d[h[x]]<d[h[(x+1)/3]]&&x>1 ){
        schimb(x,(x+1)/3);
        x=(x+1)/3;
    }
}

void down(int x){
    int top=x*3-1,mid=x*3,bot=x*3+1,lane=x;
    if ( d[h[top]]>d[h[lane]]&&top<=si )lane=top;
    if ( d[h[mid]]>d[h[lane]]&&mid<=si )lane=mid;
    if ( d[h[bot]]>d[h[lane]]&&bot<=si )lane=bot;
    if ( lane==x )return;
    schimb(lane,x);
    down(lane);
}

void ins(int x){
    h[++si]=x;
    poz[x]=si;
    up(si);
    down(si);
}

void del(int x){
    schimb(x,si);
    --si;
    down(x);
}

void prim(){
    for ( int i=1;i<n;++i ){
        rec[i].x=rec[i-1].c;
        rec[i].c=h[1];
        int x=h[1];
        s+=d[h[1]];
        d[h[1]]=-1001;
        del(1);
        for ( int j=0;j<v[x].size();++j ){
            if ( v[x][j].c<d[v[x][j].x]&&d[v[x][j].x]!=-1001 ){
                if ( d[v[x][j].x]!=1001 ){
                    d[v[x][j].x]=v[x][j].c;
                    up(poz[v[x][j].x]);
                }
                else {
                    d[v[x][j].x]=v[x][j].c;
                    ins(v[x][j].x);
                }
            }
        }
    }
}

int main(){
    fscanf(f,"%d%d",&n,&m);
    for ( int i=1;i<=n;++i )
        d[i]=1001;
    for ( int i=1;i<=m;++i ){
        int a,b,d;
        fscanf(f,"%d%d%d",&a,&b,&d);
        v[a].push_back({b,d});
        v[b].push_back({a,d});
    }
    for ( int i=0;i<v[1].size();++i ){
        d[v[1][i].x]=v[1][i].c;
        ins(v[1][i].x);
    }
    rec[0].c=1;
    d[1]=-1001;
    prim();
    fprintf(g,"%d\n%d\n",s,n-1);
    for ( int i=1;i<n;++i )
        fprintf(g,"%d %d\n",rec[i].x,rec[i].c);
    return 0;
}