#include <cstdio>
#include <vector>
#include <queue>
#include <ctype.h>

using namespace std;

#define NMAX 200015
#define maxim(a,b) ((a>b)?(a):(b))

struct Adiacency_List {
    int vertex, cost;
    bool added;
};

struct Edge_List {
    int cost, vertex1, vertex2;
};

struct APM_List {
    int father, cost, code;
};

struct Queue_comparator {

    bool operator() (const Edge_List& a, const Edge_List& b) {
        return (a.cost > b.cost);
    }
};

//vector < Adiacency_List > G[NMAX];

 priority_queue < Edge_List , vector < Edge_List> , Queue_comparator> E;

APM_List APM[NMAX];

int Origin[NMAX], HM_Nodes_of_Trees[NMAX];

char line[45];
int begin_line;

int N, M, Integrated_Vertexes, NrCode;

int Compute_Read_Values() {

    int n = 0;
    bool positive = true;

    if(line[begin_line]=='-') {
        positive = false;
        begin_line++;
    }

    while(isdigit(line[begin_line])) {
        n = n*10 + line[begin_line++] - '0';
    }

    begin_line++;

    if(!positive)
        return -n;
    return n;
}

void Read() {

    freopen("apm.in","r",stdin);

    scanf("%d%d ",&N,&M);

    int x,y,c;

    for(int i=1;i<=M;i++) {
        fgets(line,40,stdin);
        begin_line = 0;
        x=Compute_Read_Values();
        y=Compute_Read_Values();
        c=Compute_Read_Values();
        E.push({c,x,y});
    }
}

bool Compute_and_Valide_Solution(Edge_List& sol) {

    if(Origin[APM[sol.vertex1].code] == Origin[APM[sol.vertex2].code]) {
        if(Origin[APM[sol.vertex1].code])
            return false;

        // new tree
        ++NrCode;
        APM[sol.vertex1].code = APM[sol.vertex2].code = NrCode;
        //Origin[APM[sol.vertex1].code] = Origin[APM[sol.vertex2].code] = NrCode;
        Origin[APM[sol.vertex2].code] = sol.vertex1;
        APM[sol.vertex2].father = sol.vertex1;
        APM[sol.vertex2].cost = sol.cost;
        HM_Nodes_of_Trees[Origin[APM[sol.vertex2].code]] = 2;
        Integrated_Vertexes = maxim(Integrated_Vertexes, HM_Nodes_of_Trees[Origin[APM[sol.vertex2].code]]);
        return true;
    }

    // new edge to the three
    if(!Origin[APM[sol.vertex1].code] || !Origin[APM[sol.vertex2].code]) {
        if(Origin[APM[sol.vertex2].code]) {
            int tamp;
            tamp = sol.vertex1;
            sol.vertex1 = sol.vertex2;
            sol.vertex2 = tamp;
        }

        APM[sol.vertex2].code = APM[sol.vertex1].code;
        APM[sol.vertex2].father = sol.vertex1;
        APM[sol.vertex2].cost = sol.cost;
        HM_Nodes_of_Trees[Origin[APM[sol.vertex1].code]] ++;
        Integrated_Vertexes = maxim(Integrated_Vertexes, HM_Nodes_of_Trees[APM[sol.vertex2].code]);
        return true;
    }

    //reunion of threes
    HM_Nodes_of_Trees[Origin[APM[sol.vertex1].code]] += HM_Nodes_of_Trees[Origin[APM[sol.vertex2].code]];
  //  APM[Origin[APM[sol.vertex2].code]].father = Origin[APM[sol.vertex1].code];
    if(APM[sol.vertex2].father) {
        APM[Origin[APM[sol.vertex2].code]].father = sol.vertex2;
        APM[Origin[APM[sol.vertex2].code]].cost = APM[sol.vertex2].cost;
    }
    Origin[APM[sol.vertex2].code] = Origin[APM[sol.vertex1].code];
    APM[sol.vertex2].father =  sol.vertex1;
    APM[sol.vertex2].cost = sol.cost;
    Integrated_Vertexes = maxim(Integrated_Vertexes, HM_Nodes_of_Trees[APM[sol.vertex1].code]);
    return true;
}

void Minimum_Spanning_Tree() { // Kruskal's Algorithm

    Edge_List sol;

    while(Integrated_Vertexes<N) {

        sol = E.top();
        E.pop();
        if(!Compute_and_Valide_Solution(sol))
            continue;
    }

}

void Print() {

    freopen("apm.out","w",stdout);

    int Sum_of_Costs = 0;

    for(int i=1;i<=N;++i) {
        Sum_of_Costs += APM[i].cost;
    }

    printf("%d\n%d\n",Sum_of_Costs,N-1);

    for(int i=1;i<=N;++i) {
        if(i && APM[i].father)
        printf("%d %d %d\n",i,APM[i].father,APM[i].cost);
    }
}

int main() {

    Read();
    Minimum_Spanning_Tree();
    Print();
    return 0;
}