#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct graf{
       int x,y,val,id;
       }a[200003];
int n,i,k,j,m,ac=0,value=0;

char b[200003]= {0};
//int** vec = new int*[10]; 
//vec[1] = new int;
    
graf find_min(){
     int min = 9999999,curr;
     for(int i=1;i<=m;i++){
             if(b[a[i].x]+b[a[i].y] == 1  && a[i].val<min){
                              curr=i;
                              min = a[i].val;
                              }
             }
     //a[curr].val=;
     return a[curr];
     
     }
void apm(){
     graf q;
     q = find_min();
     value += q.val;
     a[q.id].val = 9999999;
     if(b[q.x]!=0)
                  b[q.y]=1;
                  else
                  b[q.x]=1;
//     cout<<""; 
     ac++;
     }
     
int comp(const void* pa, const void* pb)
 {

	const graf* a = reinterpret_cast<const graf*>(pa);
	const graf* b = reinterpret_cast<const graf*>(pb);

	return (a->val > b->val);
}
int main(){
    fin>>n>>m;
//    for(i=1;i<=n;i++) vec[i]= new int;
    for(i=1;i<=m;i++){
                       fin>>a[i].x>>a[i].y>>a[i].val;
                       a[i].id=i;
                       //v[a[i].x]++;
      //                 vec[a[i].x][v[a[i].x]] = a[i].y;
                       }
    qsort(a, m, sizeof(int), comp);
    b[1] = 1;
    //active[1]=1;
    ac = 1;
   while(ac<=n-1) apm();
    
    fout<<value<<endl<<n-1<<endl;
    
    for(int i=1;i<=m;i++)
    if(a[i].val==9999999)fout<<a[i].x<<" "<<a[i].y<<endl;
    
   
    
    //system("pause");
}