#include <fstream>
#include <vector>
std::ifstream cin("apm.in");
std::ofstream cout("apm.out");
#define it std::vector<std::pair<int,int>>::iterator
#define maxn 200050
const int inf=5000000;
int n,k,m,poz[maxn],h[maxn*2],vec[maxn],v[maxn],ans;
std::vector<std::pair<int,int>> g[maxn],vans;

void introduce_in_apm(int x){
    for(it xd=g[x].begin();xd!=g[x].end();xd++){
        int nod=xd->first;
        int cost=xd->second;
        if(v[nod]>=cost){
            v[nod]=cost;
            vec[nod]=x;
        }
    }
}

void push(int x){
    int y,aux;
    while(y!=x){
        y=x;
        if(v[h[(y<<1)+1]]<v[h[x]]&&((y<<1)+1)<=k)
            x=((y<<1)+1);
        if(v[h[y<<1]]<v[h[x]]&&(y<<1)<=k)
            x=(y<<1);
        aux=h[x];
        h[x]=h[y];
        h[y]=aux;
        aux=poz[h[x]];
        poz[h[x]]=poz[h[y]];
        poz[h[y]]=aux;

    }
}

int rad_heap(){
    int x=h[1];
    h[1]=h[k];
    poz[1]=poz[k];
    k--;
    push(1);
    poz[x]=0;
    return x;
}

void pop(int pos){
    int aux;
    while(v[h[pos]]<v[h[pos/2]]&&(pos>1)){
        aux=poz[h[pos]];
        poz[h[pos]]=poz[h[pos/2]];
        poz[h[pos/2]]=aux;
        aux=h[pos];
        h[pos]=h[pos/2];
        h[pos/2]=aux;
        pos/=2;
    }
}

void introduce_in_heap(int x){
    h[++k]=x;
    poz[x]=k;
    pop(k);
}

int main()
{
    int x,y,c;
    cin>>n>>m;
    for(;m--;){
        cin>>x>>y>>c;
        g[x].push_back(std::make_pair(y,c));
        g[y].push_back(std::make_pair(x,c));
    }
    for(int i=2;i<=n;i++)
        v[i]=inf;
    v[1]=0;
    introduce_in_apm(1);
    for(int i=2;i<=n;i++)
        introduce_in_heap(i);
    for(int i=1;i<n;i++){
        int x=rad_heap();
        introduce_in_apm(x);
        ans+=v[x];
        vans.push_back(std::make_pair(x,vec[x]));
        for(it xd=g[x].begin();xd!=g[x].end();xd++)
            if(poz[xd->first]) pop(poz[xd->first]);

    }
    cout<<ans<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        cout<<vans[i].first<<' '<<vans[i].second<<'\n';
    return 0;
}