#include<stdio.h>
#include<stdlib.h>

typedef struct {
    int x, y;
    int cost;
}EDGE;

int readEdges(EDGE *edges, char *inputFile, int *n);
void sortEdges(EDGE *edges, int m);
void print(EDGE *edges, int m, int cost);
//void initTrees(int *trees, const int n);
void combineTrees(int *trees, const int n, const int tree1, const int tree2);
int sameTree(int *trees, const int u, const int v);
void allocResult(EDGE **result, const int n);
void kruskal(EDGE *edges, const int n, const int m);

int main() {
    EDGE edges[10000];
    int n, m;

    m = readEdges(edges, "apm.in", &n);
    kruskal(edges, n, m);

    return 0;
}


void initTrees(int *trees, const int n) {
    int i;
    for(i = 0; i < n; ++i)
        trees[i] = i;
}

void combineTrees(int *trees, const int n, const int tree1, const int tree2) {
    int i;
    for(i = 0; i < n; ++i)
        if(trees[i] == tree2)
            trees[i] = tree1;
}

int sameTree(int *trees, const int u, const int v) {
    return (trees[u] != trees[v]);
}

void allocResult(EDGE **result, const int n) {
    *result = (EDGE*)malloc(sizeof(EDGE) * (n - 1));
    if(*result == NULL) {
        perror("Nu se poate aloca memorie ");
        exit(1);
    }
}

void kruskal(EDGE *edges, const int n, const int m) {
    int trees[n], i, noTrees = n, j = -1, cost = 0;
    EDGE *result;

    allocResult(&result, n);
    initTrees(trees, n);
    sortEdges(edges, m);

    for(i = 0; i < m && noTrees > 1; ++i)
        if(sameTree(trees, edges[i].x, edges[i].y)) {
            result[++j] = edges[i];
            cost += edges[i].cost;
            combineTrees(trees, n, edges[i].x, edges[i].y);
            --noTrees;
        }

    print(result, n-1, cost);
}


int readEdges(EDGE *edges, char *inputFile, int *n) {
    int i, m;
    FILE *input = fopen(inputFile, "r");
    if(input == NULL) {
        perror("Fisierul nu se poate deschide ");
        exit(1);
    }
    fscanf(input, "%d %d", n, &m);
    i = 0;
    while(1) {
        fscanf(input, "%d %d %d", &edges[i].x, &edges[i].y, &edges[i].cost);
        if(feof(input))  break;
        ++i;
    }
    return m;
}

void sortEdges(EDGE *edges, int m) {
    /* bubble sort */
    int i, j, ok = 1;
    EDGE temp;
    for(i = 0; i < m-1 && ok; ++i){
        ok = 0;
        for(j = 0; j < m-i-1; ++j)
            if(edges[j].cost > edges[j + 1].cost) {
                temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
                ok = 1;
            }
    }
}

void print(EDGE *edges, int m, int cost) {
    int i;
    FILE *f = fopen("apm.out","w");
    fprintf(f, "%d\n%d\n",cost, m);
    for(i = 0; i < m; ++i)
        printf("%d %d\n", edges[i].x, edges[i].y);
    fclose(f);
}