#include <fstream>
#include <vector>
std::ifstream cin("apm.in");
std::ofstream cout("apm.out");
#define maxn 200020
#define inf 50000
using namespace std;
int H[maxn*2],poz[maxn],v[maxn],vec[maxn],N,M,ANS,L;
vector <pair<int,int>> VECT[maxn],VANS;

void pop(int x){
    int aux;

    while(x/2&& v[H[x/2]]>v[H[x]])
    {
        aux=H[x];
        H[x]=H[x/2];
        H[x/2]=aux;

        aux=poz[H[x]];
        poz[H[x]]=poz[H[x/2]];
        poz[H[x/2]]=aux;
    }
}

void add_to_heap(int x){
    L++;
    H[L]=x;
    poz[x]=L;
    pop(L);
}


int add_to_apm(int x){
    int nod,cost;
    for(int i=0;i<VECT[x].size();i++){
        nod=VECT[x][i].first;
        cost=VECT[x][i].second;
        if(v[nod]>cost){
            v[nod]=cost;
            vec[nod]=x;
        }
    }
}

void push(int x){
    int y=0,aux;
    while(x!=y){
        x=y;
        if(x*2<=L&&v[H[x]]<v[H[x*2]])
            x=2*y;
        if(x*2+1<=L&&v[H[x]]<v[H[x*2+1]])
            x=2*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 pop_root(){
    int x=H[1];
    H[1]=H[L];
    poz[1]=poz[L];
    L--;
    poz[x]=0;
    push(1);
    return x;
}

int main()
{
    int x,y,cost;
    cin>>N>>M;

    for(;M--;){
        cin>>x>>y>>cost;
        VECT[x].push_back(make_pair(y,cost));
        VECT[y].push_back(make_pair(x,cost));
    }
    for(int i=1;i<=N;i++)
        v[i]=inf;
    v[1]=0;
    add_to_apm(1);
    for(int i=2;i<=N;i++)
        add_to_heap(i);
    for(int i=1;i<=N;i++){
        int z=pop_root();
        add_to_apm(z);
        ANS+=v[z];
        VANS.push_back(make_pair(z,v[z]));
        for(int j=0;j<VECT[z].size();j++){
            int nod=VECT[z][i].first;
            if(poz[nod]) pop(poz[nod]);
        }
    }
    cout<<ANS<<'\n'<<N-1<<'\n';
    for(int i=1;i<=N;i++){
        cout<<VANS[i].first<<' '<<VANS[i].second;
    }
    return 0;
}