#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define BIG 1000000

typedef struct muchie{
    int dist, from, to;
}muchie;

int fcmp(const void* a, const void* b);
muchie* read_file(int *N, int *M,char* file);
int find(int i, int* tati);
void unite(int *tati, int from, int to, int* rank);
void kruskal(char* in, char* out);

int main(){
    kruskal("apm.in", "apm.out");
    return 0;
}

muchie* read_file(int *N, int *M, char* file){
    FILE *f = fopen(file, "r");
    fscanf(f, "%d %d", N, M);
    //Citim vectorii cu vecini
    muchie* edges = malloc(sizeof(muchie)*(*M));
    for(int i=0;i<*M;i++){
        fscanf(f, "%d %d %d", &edges[i].from, &edges[i].to, &edges[i].dist);
    }
    fclose(f);
    return edges;
}

int fcmp(const void * a, const void* b){
    muchie* pa = (muchie*) a;
    muchie* pb = (muchie*) b;
    return (pa->dist - pb->dist);
}

void kruskal(char* in, char* out){
    int i, N, M, tati[100], rank[100];
    muchie *edges = read_file(&N,&M,in);
    for(i=1;i<=N;i++){
        tati[i] = i;
        rank[i] = 1;
    }
    int cnt=0;
    muchie final[100];
    qsort(edges, M, sizeof(muchie), fcmp);
    int total_cost = 0;
    for(i=0;i<M;i++){
        int x = find(edges[i].from, tati);
        int y = find(edges[i].to, tati);
        if(x != y){
            total_cost += edges[i].dist;
            final[cnt] = edges[i];
            cnt++;
            unite(tati, x, y, rank);
        }
    }
    FILE* f = fopen(out, "w");
    fprintf(f, "%d\n%d\n", total_cost, cnt);
    for(i=0;i<cnt;i++){
        fprintf(f, "%d %d\n", final[i].to, final[i].from);
    }
    fclose(f);
    free(edges);
}

int find(int i, int* tati){
    if(tati[i] == i){
        return i;
    }
    else{
        int aux = find(tati[i], tati);
        tati[i] = aux;
        return aux;
    }
}

void unite(int *tati, int from, int to, int* rank){
    int root1 = find(from, tati), root2 = find(to, tati);
    if(rank[root1] > rank[root2]){
        tati[root2] = root1;
    }
    else{
        tati[root1] = root2;
        if(rank[root1] == rank[root2]){
            rank[root2]++;
        }
    }
}