#include<fstream>
#define maxm 400005
#define maxn 200005
using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

int a[maxm],b[maxm],c[maxm],r[maxm];
int tata[maxn],rang[maxn];
int i,n,m;
int x,y,cost,k;

void swap3(int i,int j){
     int k;
     k=c[i]; c[i]=c[j]; c[j]=k;
     k=b[i]; b[i]=b[j]; b[j]=k;
     k=a[i]; a[i]=a[j]; a[j]=k;
}

void quick(int left, int right){
     int i,j,mid;
     mid=c[(left+right)/2];
     i=left;
     j=right;
     
     while (i<j) {
                  while (c[i]<mid) i++;
                  while (c[j]>mid) j--;
                  if (i<=j) {
                             swap3(i,j);
                             i++; j--;
                            } 
                  } 
     if (left<j) quick(left,j);
     if (i<right) quick(i,right);
}

int radacina(int x){
    int aux,q;
    q=x;
    
    while (x!=tata[x]) x=tata[x];
    while (q!=x) {aux=q; q=tata[q]; tata[aux]=x; }
    
    return x;   
}

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

int main(void){
    fi>>n>>m;
    
    for(i=1;i<=m;i++) fi>>a[i]>>b[i]>>c[i];
    for(i=1;i<=n;i++) { tata[i]=i; rang[i]=0; }
                       
    quick(1,m);

    cost=0; k=0;
    for(i=1;i<=m;i++) {
                       x=radacina(a[i]);
                       y=radacina(b[i]);
                       if (x!=y)
                          {
                           uneste(x,y);
                           k++;
                           r[k]=i;
                           cost+=c[i];
                          } 
                      }
    
    fo<<cost<<"\n";
    fo<<k<<"\n";
    for(i=1;i<=k;i++) fo<<a[r[i]]<<" "<<b[r[i]]<<"\n";
    
    fi.close();
    fo.close();
    return 0;
}