#include <fstream>
#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);

	ifstream fin("apm.in");

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

   fin>>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(); */
        fin>>x>>y>>c;
        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);

	ofstream fout("apm.out");

	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);
	fout<<Sum_of_Costs<<"\n"<<N-1<<"\n";

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

int main() {

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