#include <fstream>
#include <algorithm>
#define IN "apm.in"
#define OUT "apm.out"
#define DMAX 200008
#define VMAX 400008
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

struct Vertex{int a, b, cost;};

int n, m;
int p[DMAX];
Vertex v[VMAX];
int cost;
Vertex mst[DMAX];
int nmst;

void MAKE_SET(int);
void UNION(int, int);
void LINK(int, int);
int FIND_SET(int);
bool Compara(Vertex a, Vertex b){return a.cost<b.cost;}

void Read();
void Showtime();
void Result();

int main(){
    Read();
    Showtime();
    Result();
    return 0;
}

void Result(){
    fout <<cost<<'\n';

    fout <<nmst<<'\n';
    int i;
    for (i=1; i<=nmst; ++i){
        fout <<mst[i].a<<' '<<mst[i].b<<'\n';
    }
    fout.close();
}

void Showtime(){
    sort(v+1, v+m+1, Compara);

    int i;
    for (i=1; i<=m; ++i)
        MAKE_SET(i);

    for (i=1; i<=m; ++i){
        if (FIND_SET(v[i].a) != FIND_SET(v[i].b)){
            //il iau
            mst[++nmst]=v[i];
            cost+=v[i].cost;
            //unesc
            UNION(v[i].a, v[i].b);
        }
    }
}

void Read(){
    fin >>n>>m;

    int i;
    for (i=1; i<=m; ++i)
        fin >>v[i].a>>v[i].b>>v[i].cost;
}

void MAKE_SET(int x){
    p[x]=x;
}

void UNION(int x, int y){
    LINK(FIND_SET(x), FIND_SET(y));
}

void LINK(int x, int y){
    p[y]=x;
}

int FIND_SET(int x){
    if (p[x]!=x)
        p[x]=FIND_SET(p[x]);
    return p[x];
}