#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#define DIM 400011
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,cost;
int T[DIM];

vector<pair<int,int> > sol;
vector<pair<int,int> >::iterator it;

struct muchie{
    int x,y,c;
};
muchie v[DIM];

int cmp(muchie a,muchie b){
    return (a.c<b.c);
}

int root(int x){
    int y=x,aux;
    while(T[x]>0) x=T[x];
    while(T[y]>0) aux=y,y=T[y],T[aux]=x;
    return x;
}

int main(void){
    register int i,j,x,y;

    f>>n>>m;
    memset(T,-1,sizeof(T));
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);

    for(i=1;i<=m;i++){
        x=root(v[i].x);
        y=root(v[i].y);
        if(x!=y){
            if(T[x]<T[y]) T[x]+=T[y],T[y]=x;
            else T[y]+=T[x],T[x]=y;
            cost+=v[i].c;
            sol.push_back(make_pair(v[i].x,v[i].y));
        }
    }

    g<<cost<<"\n"<<sol.size()<<"\n";
    for(it=sol.begin();it!=sol.end();it++)
        g<<it->first<<" "<<it->second<<"\n";
    f.close();
    g.close();
    return 0;
}