#include <fstream>
#include <algorithm>
#define MMAX 400001
#define NMAX 200001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
struct Muchie{
    int x, y;
    double c;
};
Muchie G[MMAX];
int APM[NMAX];
int conex[MMAX];
int cost_APM;
int nrm;

void init();
bool crit(Muchie, Muchie);

int main(){
    init();

    int i, j, minim, maxim;
    for(i = 1; i<= m ; ++i){
        if( conex[ G[i].x ] != conex[ G[i].y ] ){

                if( conex[ G[i].x ] < conex[ G[i].y ] ){
                    minim = conex[ G[i].x ];
                    maxim = conex[ G[i].y ];
                } else {
                    minim = conex[ G[i].y ];
                    maxim = conex[ G[i].x ];
                }

                APM[++nrm] = i;
                cost_APM += G[i].c;

                for(j = 1; j<=n; ++j){
                    if( conex[j] == maxim)
                        conex[j] = minim;
                }
        }
    }

    fout<<cost_APM<<'\n'<<nrm<<'\n';
    for(i = 1; i<=n-1; ++i)
        fout<<G[ APM[i] ].x<<" "<<G[ APM[i] ].y<<'\n';
    return 0;
}

void init(){
    fin>>n>>m;
    int i;

    for(i = 1 ;i<=m; ++i)
        fin>>G[i].x>>G[i].y >>G[i].c;
    for(i = 1; i<=n; ++i)
        conex[i] = i;
    sort(G+1,G+m+1, crit);

    /*
    for(i = 1 ;i<=m; ++i)
        fout<<G[i].x<<" "<<G[i].y<<" "<<G[i].c<<"\n";
    */
}

bool crit(Muchie a, Muchie b){
    return (a.c < b.c);
}