#include<fstream>//paduri de multimi disjuncte (cu compresia drumurilor)
#include<algorithm>
#define dmax 400003
#define nmax 200003
using namespace std;
ifstream f("apm.in"); ofstream g("apm.out");
int n, m,nr,j,cost, sol[nmax], T[nmax];

struct muchie
{   int a,b,cost;} muchia[dmax];

int cmp(muchie x, muchie y)
{    return x.cost < y.cost; }

void reuneste_arb(int a, int b)
{
     T[a] = b;
}
int rad(int x)
{
    int r, y;
    r=x;                 //merg in sus pe arbore pana gasesc radacina
    while(T[r]!=0)r=T[r];// un nod cu tata 0)

    while(T[x]!=0)     //aplic compresia drumurilor
      {  y = T[x]; T[x] = r;  x = y;  }
    return r; //returnez radacina
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++) f>>muchia[i].a>>muchia[i].b>>muchia[i].cost;
    sort(muchia+1, muchia+m+1, cmp);
    j=1; cost=0;
    while(nr < n-1)
    {
        while(rad(muchia[j].a)==rad(muchia[j].b))
                             j++;
        nr++;
        sol[nr] = j;
        cost += muchia[j].cost;
        reuneste_arb(rad(muchia[j].a), rad(muchia[j].b));
    }
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(int i=1; i<n; i++)g<<muchia[sol[i]].a<<" "<<muchia[sol[i]].b<<'\n';
    return 0;
}
//
////Bellman Ford O(m*n) 100p
//#include<fstream>
//#define inf 1000000
//#define NMax 100003
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//struct Nod{
//    int nod, cost;
//    Nod *next;
//};
//Nod *t,*L[NMax];
//int pr,p,i,j,m,n,x,y,costul,nod,d[NMax],coada[5*NMax];
//void adauga(int x, int y, int costul){
//    Nod *q = new Nod;
//    q->nod = y;
//    q->cost = costul;
//    q->next = L[x];
//    L[x] = q;
//}
//
//void bellman_ford(int x){
//    int p,u,i;
//    for(i=1;i<=n;i++) d[i]=inf;
//    p=1;u=1;
//    coada[u]=x;
//    d[x]=0;
//    while (p<=u)
//     {
//        j=coada[p];p++;
//        t=L[j];
//        while(t){
//           if(d[t->nod]>d[j]+t->cost)
//            {
//                coada[++u]=t->nod;
//                d[t->nod]=d[j]+t->cost;
//            }
//           t=t->next;
//        }
//    }
//}
//
//int main()
//{   int i;
//    f>>n>>m;
//    for(i=1;i<=m;i++)
//     {
//        f>>x>>y>>costul;
//        adauga(x,y,costul);
//        adauga(y,x,costul);
//     }
//    bellman_ford(1);
//    for ( int i = 1; i <= n; i++ )
//        if(d[i] == inf) g<<-1<<" ";
//        else g<< d[i]<<" ";
//    f.close();   g.close();
//}
//
//
////Bellman Ford O(m*n) 100p
//#include<fstream>
//#define inf 1000000000
//#define NMax 103
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//long long  p,j,m,n,x,y,costul,nod,d[NMax],coada[5*NMax];
//int c[NMax][NMax];
//void bellman_ford(int nod_pornire){
//    int p,u,i;
//    for(i=1;i<=n;i++) d[i]=inf;
//    d[nod_pornire]=0;
//    p=1;u=1; coada[u]=nod_pornire;
//    while (p<=u)
//     {
//        j=coada[p];
//        p++;
//        for(i=1;i<=n;i++)
//            if(c[j][i]>0)
//            if(d[i]>d[j]+c[j][i])
//                {
//                    d[i]=d[j]+c[j][i];
//                    coada[++u]=i;
//                }
//    }
//}
//int main()
//{
//    f>>n>>p;
//    while(f>>x>>y>>costul)
//        c[x][y]=costul;
//    bellman_ford(p);
//    for ( int i = 1; i <= n; i++ )
//        if(d[i] == inf) g<<-1<<" ";
//        else g<< d[i]<<" ";
//    f.close(); g.close();
//}


//#include <iostream>
//#define M 103
//using namespace std;
//int k,x,y,i,j,n,m,gri[M],gre[M];
//int main()
//{
//    cin>>n>>m;
//    for(i=1;i<=m;i++){
//        cin>>x>>y;gre[x]++;gri[y]++;
//    }
//    for(i=1;i<=n;i++)
//        if(gri[i]==gre[i])k++;
//    cout<<k<<endl;
//    for(i=1;i<=n;i++)
//        if(gri[i]==gre[i])cout<<i<<" ";
//    return 0;
//}
//#include<fstream>
//#include<iomanip>
//using namespace std;
//ifstream fi("camelot.in");
//ofstream fo("camelot.out");
//int coada[1000003];
//const int x[8]={-1,1,2,2,1,-1,-2,-2};
//const int y[8]={2,2,1,-1,-2,-2,-1,1};
//int n,a[1001][1001],t,m,j,i,sol,xx,yy,cer,k,xc,yc,l,c;
//
//void BFS(int p,int q)
//{
//int l,c,i,j,prim,ultim,ll,cc;
//coada[1]=p*10000+q;
//prim=ultim=1;
//while(prim<=ultim){
//    l=coada[prim]/10000;
//    c=coada[prim]%10000;
//    prim++;
//    for(i=0;i<=7;i++)
//      {
//          ll=l+x[i];
//          cc=c+y[i];
//          if((ll>=1)&&(ll<=m)&&(cc>=1)&&(cc<=n)&&(a[ll][cc]==0 or a[ll][cc]==-1))
//                {
//                  a[ll][cc]=a[l][c]+1;
//                  ultim++;                                           //se bifeaza pozitia
//                  coada[ultim]=ll*10000+cc;
//                }
//      }
//  }
//}
// int  main()
// {
//fi>>cer;
//fi>>m>>n>>k;
//fi>>xc>>yc;
//a[xc][yc]=1;
//BFS(xc,yc);
//int maxi,mini;
//mini=1000000;
//maxi=-1000000;
//for(int t=1;t<=k;t++)
//    { fi>>i>>j;
//      if(a[i][j]>maxi)maxi=a[i][j];
//      if(a[i][j]<mini)mini=a[i][j];
//    }
//if(cer==1) fo<<mini-1;
//if(cer==2) fo<<maxi-1;
////fo<<endl;
////for(i=1;i<=m;i++){
////    for(j=1;j<=n;j++)fo<<setw(3)<<a[i][j];
////    fo<<endl;
////}
// return 0;
// }