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

struct muchie
{
    int vi,vf;
    double cost;
};

struct muchie_min_varf{
    int varf;
    double 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;
}


double cost_total = 0;

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


    //*initializare d,tata,viz
    d=new double[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;


    set <pair<double,int>> Q;
    Q.insert({d[s],s});
   // for(i=1; i<=n-1; i++)
    //{
   while(!Q.empty()){
       //varful nevizitat cu d minim
        u=Q.begin()->second;
        Q.erase(Q.begin());
        if(viz[u]==0)
        {

        viz[u]=1;

        //actualizam etichetele vecinilor nevizitati
        for(int j=0; j< (int)la[u].size(); j++)
        {
            v=la[u][j].first;
            w_uv=la[u][j].second;
            if(viz[v]==0)
            {

                if(d[v]>w_uv)
                {
                    tata[v]=u;
                    d[v]=w_uv;
                    Q.insert(make_pair(d[v],v)); //adaug noua pereche v,d[v]
                }
            }
        }
       }
    }

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

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

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

    la=new vector < pair <int,double> >[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;

}