#include <stdio.h>
#include <stdlib.h>
typedef struct type_node{
int key, weight;
struct type_node * next;
} node;

typedef struct type_edge{
int nod1, nod2, weight;
struct type_edge *next;
} edge;

typedef struct type_queue{
edge *first, *last;
} queue;

void enqueue(queue* q, int a, int b, int w){
    edge *nou=calloc(1, sizeof(edge));
    nou->nod1=a;
    nou->nod2=b;
    nou->weight=w;
    if(!q->first){
        q->first=q->last=nou;
        return;
    }

if(w<q->first->weight){
    nou->next=q->first;
    q->first=nou;
    return;
}
if(w>q->last->weight){
    q->last->next=nou;
    q->last=nou;
    return;
}
edge *anterior, *actual;
anterior=q->first;
actual=q->first->next;
while(actual){
    if(w<actual->weight){
        nou->next=actual;
        anterior->next=nou;
        return;
    }
    anterior=actual;
    actual=actual->next;
}
}

edge *dequeue(queue *q){
edge *prim=q->first;
q->first=q->first->next;
return prim;
}

node** citire_graf_fisier(FILE *pf, int n){
node** graph=calloc(n+1, sizeof(node*));
int n1, n2, w;
while(fscanf(pf, "%d %d %d", &n1, &n2, &w)!=EOF){
    node*nou=calloc(1, sizeof(node));
    nou->key=n2;
    nou->weight=w;
    nou->next=graph[n1];
    graph[n1]=nou;

    nou=calloc(1, sizeof(node));
    nou->key=n1;
    nou->weight=w;
    nou->next=graph[n2];
    graph[n2]=nou;
}
return graph;
}

int prim_alg(node** graph, int n, FILE *pf){
int vizitat, cost=0;
char *arbore=calloc(n+1, sizeof(char));
arbore[1]='v';
vizitat=1;
queue *q=calloc(1, sizeof(queue));
node *aux;
while(graph[1]){
    enqueue(q, 1, graph[1]->key, graph[1]->weight);
    aux=graph[1];
    graph[1]=graph[1]->next;
    free(aux);
}
edge *muchie;
while(vizitat<n){
    muchie=dequeue(q);
    if(!arbore[muchie->nod2]){
    vizitat++;
    arbore[muchie->nod2]='v';
    fprintf(pf, "%d %d\n", muchie->nod1, muchie->nod2);
    cost+=muchie->weight;
while(graph[muchie->nod2]){
        if(!arbore[graph[muchie->nod2]->key])
        enqueue(q, muchie->nod2, graph[muchie->nod2]->key, graph[muchie->nod2]->weight);
        aux=graph[muchie->nod2];
        graph[muchie->nod2]=graph[muchie->nod2]->next;
        free(aux);
}
}
}
free(arbore);
return cost;
}

node **g; int n, m, cost;
int main()
{   FILE *pf=fopen("apm.in", "r");
    fscanf(pf, "%d %d", &n, &m);
    g=citire_graf_fisier(pf, n);
    fclose(pf);
     pf=fopen("apm.out", "w");
    fprintf(pf, "           \n");
     fprintf(pf, "%d\n", n-1);
    cost=prim_alg(g, n, pf);
    fseek(pf, 0, SEEK_SET);
    fprintf(pf, "%d", cost);
    fclose(pf);
    return 0;
}