#include <bits/stdc++.h>
#define nmax 400014

using namespace std;


vector <pair<int,int>>much  ;

int n,m,sum,tata[nmax],rang[nmax],i,x,y,cost;

struct muchii
{

    int x,y,cost;

}vect[nmax];

struct comp
{
    bool operator()( const muchii &x, const muchii &y)const
    {
        return x.cost<y.cost;
    }
};


int stramos(int nod)
{
    int aux;
    int r=nod;
    while(r!=tata[r])
        r=tata[r];
    while(nod!=tata[nod])
    {
        aux=tata[nod];
        tata[nod]=r;
        nod=aux;
    }
    return r;

}

void unim(int i,int j)
{
    i=stramos(i);
    j=stramos(j);
    if(i==j)
        return ;
    if(rang[i]>rang[j])
    {
        rang[i]=rang[i]+rang[j];
        tata[j]=tata[i];

    }
    else
    {
        rang[j]=rang[j]+rang[i];
        tata[i]=tata[j];
    }

}

int main()
{

    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        vect [i].x=x ;
        vect [i].y=y ;
        vect [i].cost =cost;
    }
    sort(vect+1,vect+m+1,comp());//sortam vectorul muchiilor
    for(i=1;i<=n;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        if(stramos (vect[i].x)==stramos (vect[i].y))
            continue;

      unim(vect[i].x,vect[i].y);//capetele muchiei care va intra in arbore
      sum=sum+vect[i].cost;//suma la care se adauga muchia curenta cu un anumit cost
      much.push_back(make_pair(vect[i].x,vect[i].y));
    }
      g<<sum<<'\n';
      g<<n-1<<'\n';
       for(auto a:much)
           g<<a.second<<' '<<a.first<<'\n';

    return 0;


}