#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){
if(!(q->first)) return 0;
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){
//printf("%d %d %d\n", n1, n2, w);
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);
//printf("%d %d %d\n",muchie->nod1, muchie->nod2, muchie->weight);
if(muchie&&!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);
}
}
else{
if(!muchie) break;
}
}
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;
}