using namespace std;
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
#define oo 0x3f3f3f3f
#define left 2*po
#define right 2*po+1
#define tata po/2
struct edge{
int nod,lg;};
struct muchie
{
    int x,y;

};
ofstream fout("apm.out");
vector<edge> G[200005];
vector<muchie> muchii;
int N,M,L;
int H[200005],V[200005],ante[200005],poz[200005];

void upheap(int po)
{
 while(tata>=1 && V[H[tata]]>V[H[po]] )
 {
     swap(H[tata],H[po]);
     swap(poz[H[tata]],poz[H[po]]);
     po=tata;

 }
}
void combina(int po)
{  //cout<<left<<" ";
    while(((V[H[po]]>V[H[left]])&&(left<=L))||((V[H[po]]>V[H[right]])&&(right<=L)))
    {
        if((V[H[left]]<V[H[right]])||(right>L))
        {
            swap(H[po],H[left]);
            swap(poz[H[po]],poz[H[left]]);
            po=left;
        }
        else
        {
             swap(H[po],H[right]);
             swap(poz[H[po]],poz[H[right]]);
             po=right;

        }

    }

}


int extrage_minim()
{
   int x=H[1];
   //swap(H[1],H[L]);
   H[1]=H[L];
   H[L]=x;
   swap(poz[H[1]],poz[H[L]]);
   //poz[H[1]]=1;
    L--;
    combina(1);

    poz[x]=0;

    return x;

}

void relax(int x)
{
 vector<edge>::iterator it;
   for(it=G[x].begin();it!=G[x].end();it++)
   {
       if(V[it->nod]>it->lg)
         {V[it->nod]=it->lg;
         ante[it->nod]=x;}
         //cout<<it->nod<<" ";

   }
}

void solve()
{int i,u,raspuns=0;
    vector<edge>::iterator it;
/*for(int j=1;j<=N;j++)
          cout<<H[j]<<" ";
        cout<<"\n \n \n ";*/
    u=extrage_minim();
    relax(u);
    for(it=G[u].begin();it!=G[u].end();it++)
        {   if(poz[it->nod])////////////////////////////////////////////
            upheap(poz[it->nod]);
        }
   for(i=1;i<N;i++)
    {
          /*      for(int j=1;j<=N;j++)
         {

          cout<<H[j]<<" ";
          if(j==L)
          cout<<": ";
         }*/

        u=extrage_minim();
       // cout<<"  vvv  ";
             // for(int j=1;j<=N;j++)
        // {

          //cout<<H[j]<<" ";
          //if(j==L)
          //cout<<": ";
         //}
        raspuns+=V[u];
        //cout<<"::"<<V[u]<<" : "<<u<<"\n \n \n ";
        //V[u]=oo;

        relax(u);

        muchii.pb((muchie){u,ante[u]});

        for(it=G[u].begin();it!=G[u].end();it++)
        {   if(poz[it->nod]>0)////////////////////////////////////////////
            upheap(poz[it->nod]);
        }
    }
    //cout<<"\n\n\n\n";
    fout<<raspuns<<"\n";
    fout<<N-1<<"\n";
    for(i=0;i<=N-2;i++)
    {
        fout<<muchii[i].x<<" "<<muchii[i].y<<"\n";
    }


}
void init()
{int i;

    H[1]=1;
    poz[1]=1;
    V[1]=1;

    for(i=2;i<=N;i++)
    {
        H[i]=i;
        poz[i]=i;
        V[i]=oo;
        ante[i]=0;

    }
}
void cit(){int i,x,y,c;
    ifstream fin("apm.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        G[x].pb((edge){y,c});
        G[y].pb((edge){x,c});

    }
    fin.close();
     L=N;
}

int main()
{

    cit();
    init();
    solve();
    fout.close();

    return 0;
}