#include<fstream>
#include<algorithm>
#define maxn 200005
#define maxm 400005
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");

struct muchie{
       int x;
       int y;
       int cost;
       };
       
int tata[maxn],rang[maxn];
int i,n,m,x,y,s=0;
int r[maxn],k=0;
muchie e[maxm];

bool comp(muchie a,muchie b){
     return(a.cost<b.cost);
}

int radacina(int x){
    while(x!=tata[x]) x=tata[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(){
    fi>>n>>m;
    for(i=1;i<=m;i++) fi>>e[i].x>>e[i].y>>e[i].cost;
    
    for(i=1;i<=n;i++){ tata[i]=i; rang[i]=1; }

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