#include<stdio.h>
#include<stdlib.h>
using namespace std;
#include<algorithm>
#include<vector>
#define FIN "apm.in"
#define FOUT "apm.out"
#define NMAX 200001
#define MMAX 400001

int n,m,tata[NMAX],r[NMAX];
vector< pair<int,int> > rez;
struct muchii
{pair<int,int> e;
 int cost;
       } M[MMAX];
 
int comp(muchii e1,muchii e2)
{
    return e1.cost < e2.cost;
    }

int caut(int x)
{   int y,z;
    for(y=x;tata[y]!=y;y=tata[y]);
    for(;tata[x]!=x;)
    {z=tata[x];
     tata[x]=y;
     x=z;}
    return y;
    }        

void unite(int x,int y)
{
     if(r[x]>r[y]) tata[y]=x;
     else tata[x]=y;
     if(r[x]==r[y]) r[x]++;
     }       

int main()
{   
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
     {int x,y,c;
      scanf("%d %d %d",&x,&y,&c);
      M[i].e.first=x;
      M[i].e.second=y;
      M[i].cost=c;      
      r[i]=1;
      tata[i]=i;
            }
    sort(M+1,M+m+1,comp);        
    int nr_much=0;
    int cost_t=0;
  for(int i=1;i<=m && nr_much<n-1 ;i++)
  {       int x=M[i].e.first,y=M[i].e.second;
          if(caut ( x ) != caut (y)) 
          unite(caut(x),caut(y)),cost_t+=M[i].cost,rez.push_back(make_pair(x,y)),nr_much++;
  }
  printf("%d\n%d\n",cost_t,n-1);
  vector< pair<int,int> >::iterator it;
  for( it=rez.begin() ; it!=rez.end() ;it++ )
   printf("%d %d\n",it->first,it->second);
    return 0;
    }