#include <fstream>
#include <algorithm>

using namespace std;

int noduri[200002];
int h[200002];

int find(int x)
{
//    cout<<"startf"<<endl;
    int r=x;
    int y=x;
    int t;
    while(noduri[r])
      r=noduri[r];  
    
    while(y!=r)
    {
       t=noduri[y];
       noduri[y]=r;
       y=t;           
    }
    //cout<<"endf"<<endl;
    return r;
}

void uneste(int x,int y)
{
    //cout<<"startu"<<endl;
   x=find(x);
   y=find(y);
   
   if(h[x]<h[y])
     noduri[x]=y;
   else
   {
     noduri[y]=x;
     if(h[x]==h[y])
       h[y]++;     
   }     
    //cout<<"endu"<<endl;
}

struct muchie
{
   int cap;
   int coada;
   int lung;       
};

bool operator<(const muchie &a,const muchie &b)
{
   if(a.lung<b.lung)
     return 1;
   return 0;     
}

muchie v[400002];
muchie sol[200002];
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    
    int n,m,i;
    int poz=0; 
    
    fin>>n>>m;
    for(i=0;i<m;i++)
      fin>>v[i].cap>>v[i].coada>>v[i].lung;
      
    sort(v,v+m);
    int sum=0;
    n--;
    
    for(i=0;i<m && poz<n;i++)
    {
        if(find(v[i].cap)!=find(v[i].coada))
        {
           sol[poz++]=v[i];
           sum+=v[i].lung;
           uneste(v[i].cap,v[i].coada);                                    
        }            
    }
    fout<<sum<<'\n';
    fout<<poz<<'\n';
    for(i=0;i<poz;i++)
      fout<<sol[i].coada<<' '<<sol[i].cap<<'\n'; //cout<<sol[i].cap<<' '<<sol[i].coada<<'\n'; - La fel
    
    fin.close();
    fout.close();
    //system("PAUSE");
    return 0;
}