#include <cstdio>
#include <vector>
#include <queue>

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];

int N, M, Remained_Vertexes;

void Read() {

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

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

    int x,y,c;
    Adiacency_List tamp;
    tamp.added = false;

    for(int i=1;i<=M;i++) {
        scanf("%d%d%d",&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);

	int Sum_of_Costs = 0;

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

	printf("%lld\n",Sum_of_Costs);
	printf("%d\n",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;
}