#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
# define infinit numeric_limits<int>::infinity();
using namespace std;

struct muchie
{
    int vi,vf;
    int cost;
    muchie(int vin=0,int vfi=0,int costul=0)
    {
        vi=vin;
        vf=vfi;
        cost=costul;
    }
        bool operator <(const muchie mv) const{
        if(cost!=mv.cost)
        return (cost < mv.cost);
        if(vi!=mv.vi)
        return vi<mv.vi;
        return vf<mv.vf;
    }
};

struct muchie_min_varf{
    int varf;
    int d;
    bool operator <(const muchie_min_varf &mv) const{
        return (d < mv.d);
    }


};

struct comparator_muchie_min_varf{
bool operator()(const muchie_min_varf &mv1, const muchie_min_varf &mv2) const{
        return mv1.d<mv2.d;
    }
};


void afis(muchie m, ofstream &g)
{
    g<<m.vi << " " <<m.vf<<endl;
}


int cost_total = 0;

void Prim(int s, int n, vector<pair<int,int>> *la,  vector<muchie> &muchii_apcm)
{
    int u,  *tata, *viz,i,v;
    int *d,cost_muchie;


    d=new int[n+1];
    tata=new int[n+1];
    viz=new int[n+1];

    for(u=1; u<=n; u++)
    {
        viz[u]=tata[u]=0;
        d[u]=infinit;
    }
    d[s]=0;
    viz[s]=1;
//*
    set <muchie> Q;
    for(int i=0;i<la[s].size();i++)
    Q.insert(muchie(s,la[s][i].first,la[s][i].second));
   // for(i=1; i<=n-1; i++)
    //{
   while(!Q.empty()){

        muchie mcurr=(*Q.begin());
        Q.erase(Q.begin());
    //    cout<<mcurr.vi<<" "<<mcurr.vf<<" "<<mcurr.cost<<"\n";
        if(viz[mcurr.vf]==0)
        {

        viz[mcurr.vf]=1;
        tata[mcurr.vf]=mcurr.vi;
        d[mcurr.vf]=d[mcurr.vi]+mcurr.cost;
        cost_total+=mcurr.cost;
        for(int i=0;i<la[mcurr.vf].size();i++)
        {
        Q.insert(muchie(mcurr.vf, la[mcurr.vf][i].first,  la[mcurr.vf][i].second) );
      //  if(mcurr.vf==9)
        //    cout<<"*"<<mcurr.vf<<" "<<la[mcurr.vf][i].first<<" "<<la[mcurr.vf][i].second<<"*\n";
        }
        }

    }

    for(u=1; u<=n; u++)
        if(tata[u]!=0) {
             muchii_apcm.push_back({u,tata[u],d[u]});
        }

}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int m,n,mc, x,y,i;
    int c;

    f>>n;
    f>>m;
    vector<pair <int,int> > *la;

    la=new vector < pair <int,int> >[n+1];//graf- memorat cu liste de adiacenta


    //citim muchiile
    for(i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        la[x].push_back(make_pair(y,c));
        la[y].push_back(make_pair(x,c));
    }

    f.close();



    vector <muchie> muchii_apcm;
    Prim(1,n,la,muchii_apcm);

    g<<cost_total<<endl << muchii_apcm.size() << endl;
        for(mc=0; mc< (int)muchii_apcm.size(); mc++)
        {
            afis(muchii_apcm[mc],g);

        }
    g.close();


    return 0;

}