#include <fstream>
#include <cstdlib>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct Edge{
int from,to,cost;
};

struct Graph{
int V,E;

struct Edge* edge;
};

struct Graph* createGraph(int V, int E){
struct Graph* graph = new Graph;

graph->V = V;
graph->E = E;
graph->edge = new Edge[E];

return graph;
};

struct subset{
int parent,rank;
};

int find(struct subset subsets[], int i){
if(subsets[i].parent != i)
    subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

void Union(struct subset subsets[], int x, int y){
int xroot = find(subsets,x);
int yroot = find(subsets,y);

if(subsets[xroot].rank < subsets[yroot].rank)
    subsets[xroot].parent = yroot;
else if(subsets[xroot].rank > subsets[yroot].rank)
    subsets[yroot].parent = xroot;
else {
    subsets[yroot].parent = xroot;
    subsets[xroot].rank++;
}
}

int myComp(const void* a, const void* b){
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;

return a1->cost > b1->cost;
}

void KruskalAPM(struct Graph* graph){
int V = graph->V;
struct Edge result[V];
int e = 0;
int i = 0;

qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);

struct subset *subsets = (struct subset*)malloc(V * sizeof(struct subset));

for(int v = 0; v < V; ++v){
    subsets[v].parent = v;
    subsets[v].rank = 0;
}
int total = 0;

while(e < V-1){
    struct Edge next_edge = graph->edge[i++];

    int x = find(subsets, next_edge.from);
    int y = find(subsets, next_edge.to);

    if(x != y){
        result[e++] = next_edge;
        Union(subsets,x,y);
    }
}

for(int i=0;i<e;++i)
    total += result[i].cost;
g<<total<<'\n';
g<<e<<'\n';
for(int i=0;i<e;++i)
    g<<++result[i].from<<" "<<++result[i].to<<'\n';
}

int main(){
int n,m;
f>>n>>m;

struct Graph* graph = createGraph(n,m);
for(int i=0;i<m;++i){
    f>>graph->edge[i].from>>graph->edge[i].to>>graph->edge[i].cost;
    graph->edge[i].from--;
    graph->edge[i].to--;
}

KruskalAPM(graph);

return 0;
}