#include <fstream>
#include <vector>
#define NMAX 200000
#define INF 1001
using namespace std;

FILE * fin = fopen("apm.in", "r");
FILE * fout = fopen("apm.out", "w");

int n, m;
struct vecin{
    vector<int> v;
    vector<int> c;
};
vecin G[NMAX];

int cmin[NMAX], prec[NMAX], Z[NMAX];
int cost_apm;

void init();
void prim(int);

int main(){
    init();
    prim(1);
    return 0;
}

void init(){
    fscanf(fin,"%d %d",&n, &m);

    int i, x, y, c;
    for(i = 1; i <= m; ++i){
        fscanf(fin,"%d %d %d", &x, &y, &c);
        G[x].v.push_back(y);
        G[y].v.push_back(x);

        G[x].c.push_back(c);
        G[y].c.push_back(c);
    }

    /*
    for(i = 1; i<=n; ++i){
        if(G[i].v.size() != G[i].c.size())
            fout<<"PUSH_BACK PROBLEM!!!";
    }*/

    for(i = 1; i<=n; ++i)
        cmin[i] = INF;
}

void prim(int vfs){
    int i;
    for(i = 0; i< G[vfs].c.size(); ++i){
        cmin[ G[vfs].v[i] ] = G[vfs].c[i];
        prec[ G[vfs].v[i] ] = vfs;
    }

    int nrv = 1; Z[vfs] = 1;
    int cost_minim, vfmin;
    while(nrv <= n-1){
        cost_minim = INF;
        for(i = 1; i<= n; ++i){
            if(!Z[i] && cmin[i] < cost_minim){
                vfmin = i;
                cost_minim = cmin[vfmin];
            }
        }
        //if(cost_minim == INF) break;
        Z[vfmin] = 1; cost_apm += cost_minim; ++nrv;

        for( i = 0; i < G[vfmin].v.size(); ++i){
            if( cmin[ G[vfmin].v[i] ] > G[ vfmin ].c[i] && !Z[ G[vfmin].v[i] ] ){
                cmin[ G[vfmin].v[i] ] = G[ vfmin ].c[i];
                prec[ G[vfmin].v[i] ] = vfmin;
            }
        }

    }
    fprintf(fout,"%d %d\n",cost_apm,n-1);
    for(i = 1; i<=n; ++i){
        if(prec[i]){
            fprintf(fout,"%d %d\n", i, prec[i]);
        }
    }
}