#include <cstdio>
#include <vector>
#include <queue>
#include <ctype.h>
 
using namespace std;
 
#define NMAX 200015
 
struct Adiacency_List {
    int vertex, cost;
    bool added;
};
 
struct Edge_List {
    int cost, vertex1, vertex2;
};
 
struct Queue_comparator {
 
    bool operator() (const Edge_List& a, const Edge_List& b) {
        return (a.cost > b.cost);
    }
};
 
struct APM_List {
    int father, cost;
};
 
vector < Adiacency_List > G[NMAX];
 
priority_queue < Edge_List , vector < Edge_List> , Queue_comparator> E;
 
APM_List APM[NMAX];
 
char line[45];
int begin_line;
 
int N, M, Remained_Vertexes;
 
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();
        G[x].push_back({y,c,false});
        G[y].push_back({x,c,false});
    }
}
 
void Add_Addiacent_Vertexes_to_Queue(int vertex) {
 
    vector < Adiacency_List > :: iterator it;
 
    for(it = G[vertex].begin(); it != G[vertex].end(); ++it) {
 
        if(!(it->added))
        {
            it->added = true;
            E.push({it->cost,vertex,it->vertex});
        }
    }
}
 
bool Compute_Best_Solution(Edge_List& sol) {
 
    if(APM[sol.vertex2].father) { // e deja in APM
        if(APM[sol.vertex1].father)
            return false;
        int tamp;
        tamp = sol.vertex1;
        sol.vertex1 = sol.vertex2;
        sol.vertex2 = tamp;
    }
 
    return true;
}
 
void Minimum_Spanning_Tree() {
 
    Remained_Vertexes = N-1;
    APM[1].father = -1;
    Add_Addiacent_Vertexes_to_Queue(1);
 
    Edge_List best_sol;
 
    while(Remained_Vertexes) {
 
        best_sol = E.top();
        E.pop();
        if(!Compute_Best_Solution(best_sol))
            continue;
        APM[best_sol.vertex2].father = best_sol.vertex1;
        APM[best_sol.vertex2].cost = best_sol.cost;
        Add_Addiacent_Vertexes_to_Queue(best_sol.vertex2);
        Remained_Vertexes--;
    }
 
}
 
void Print() {
 
    freopen("apm.out","w",stdout);
 
    int Sum_of_Costs = 0;
 
    for(int i=2;i<=N;++i) {
        Sum_of_Costs += APM[i].cost;
    }
 
    printf("%d\n%d\n",Sum_of_Costs,N-1);
 
    for(int i=2;i<=N;++i) {
        printf("%d %d\n",i,APM[i].father);
    }
}
 
int main() {
 
    Read();
    Minimum_Spanning_Tree();
    Print();
    return 0;
}


/*

// Kruskal's Algorithm // not working

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

using namespace std;

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


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);
    }
};

 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.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[Origin[APM[sol.vertex1].code]]);
        return true;
    }

    //reunion of threes
    HM_Nodes_of_Trees[Origin[APM[sol.vertex1].code]] += HM_Nodes_of_Trees[Origin[APM[sol.vertex2].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) {
        if(APM[i].father)
            Sum_of_Costs += APM[i].cost;
    }

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

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

int main() {

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

*/