#include<iostream>
#include<stdio.h>
#define maxm 40000
using namespace std;

typedef struct muchie{
        int cap1, cap2, cost, apm;
        };
        
muchie v[maxm];
int n, m, compconex[maxm], costarbore=0;

int find(int i)
{if(compconex[i]!=i)
   compconex[i]=find(compconex[i]);
return compconex[i];
}
       
void swap(muchie &a, muchie &b)
{muchie aux=a;
a=b;
b=aux;
}

void quicksort(muchie v[], int start, int end) 
{int i=start;
int j=end;
int pivot=v[i+rand()%(j-i)].cost;

while(i<=j)
     {while(v[i].cost<pivot)
           i++;
      while(v[j].cost>pivot)
           j--;
      if(i<=j)
        {swap(v[i], v[j]);
         i++;
         j--;
        }
     }
     
if(start<j)
  quicksort(v, start, j);
if(i<end)
  quicksort(v, i, end);
}       
       
int main()
{freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
scanf("%d", &n);
scanf("%d", &m);

for(int i=1; i<=m; i++)
   {scanf("%d", &v[i].cap1);
    scanf("%d", &v[i].cap2);
    scanf("%d", &v[i].cost);
    compconex[i]=i;
   }
   
srand(time(NULL));
quicksort(v, 1, m);
            
for(int i=1, k=1; i<=m && k<n; i++)
   {if(compconex[v[i].cap1]!=compconex[v[i].cap2])
      {compconex[find(v[i].cap1)]=find(v[i].cap2);
       v[i].apm=1;
       costarbore+=v[i].cost;
       k++;
      }
   }

printf("%d\n%d\n", costarbore, n-1);   
for(int i=1; i<=m; i++)
   if(v[i].apm==1)
     printf("%d %d\n", v[i].cap2, v[i].cap1);
return 0;
}