#include <fstream>
#define NMAX 200002
#define MMAX 400002

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie{int x, y, cost;
              //Overloading operators
              friend bool operator < (Muchie a, Muchie b);
              friend bool operator > (Muchie a, Muchie b);
              friend bool operator >= (Muchie a, Muchie b);
              friend bool operator <= (Muchie a, Muchie b);
             };
bool operator < (Muchie a, Muchie b){
    return a.cost<b.cost;
}
bool operator > (Muchie a, Muchie b){
    return a.cost>b.cost;
}
bool operator >= (Muchie a, Muchie b){
    return a.cost>=b.cost;
}
bool operator <= (Muchie a, Muchie b){
    return a.cost<=b.cost;
}

int n,m,nrsel,costtotal;
Muchie H[MMAX];
Muchie A[MMAX];
int tata[NMAX], h[NMAX];
int Find(int x);    ///Returneaza radacina din care face parte x
void Union(int x, int y);///Reuneste arborele lui x cu arborele lui y
void creare();
void afisare();
void combinare(int n, Muchie H[], int poz);
Muchie extrageMin(int &n, Muchie H[]);

int main(){Muchie mmin; int cx,cy;
    // citire(n, H);
    creare();//Heapul este creat
    while(nrsel<n-1){
        mmin = extrageMin(m, H);
        cx = Find(mmin.x);
        cy = Find(mmin.y);
        if(cx != cy){
            nrsel++;
            A[nrsel] = mmin;
            costtotal += mmin.cost;
            Union(cx,cy);
        }
    }
    afisare();
    return 0;
}

void afisare(){int i;
    fout<<costtotal<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<n;i++)
        fout<<A[i].y<<' '<<A[i].x<<'\n';
    fout.close();
}

void inserare(int& n, Muchie H[], Muchie x){int tata, fiu;
    fiu=++n; tata=fiu/2;
    while(tata && H[tata]>x){
        H[fiu]=H[tata];
        fiu=tata;
        tata=fiu/2;
    }
    H[fiu]=x;
}

void combinare(int n, Muchie H[], int poz){Muchie x=H[poz];int fiu, tata;
    tata=poz;
    fiu=2*tata;
    while(fiu<=n){
        if(fiu+1<=n && H[fiu+1]<H[fiu]) fiu++;
        if(x <= H[fiu]) break;
        H[tata]=H[fiu];
        tata=fiu;
        fiu=2*tata;
    }
    H[tata]=x;
}

void creare(){int i;
    fin>>n>>m;
    for(i=1; i<=m; i++) fin>>H[i].x>>H[i].y>>H[i].cost;
    for(i=m/2; i>0; i--) combinare(m, H, i);
}

Muchie extrageMin(int &n, Muchie H[]){Muchie minim=H[1];
    H[1]=H[n--];
    combinare(n,H,1);
    return minim;
}

int Find(int x){int aux, rad;
    rad = x;
    while(tata[rad]) rad = tata[rad];
    ///Compresia drumului
    while(tata[x]){
        aux = tata[x];
        tata[x] = rad;
        x = aux;
    }
    return rad;
}

void Union(int x,int y){
    x = Find(x); y = Find(y);
    if(h[x]<h[y]) tata[x] = y;
    else{
        tata[y] = x;
        if(h[x] == h[y]) h[x]++;
    }
    ///O(1)
}