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

struct edge
{
    int x, y, c, s;
};

int cmpfunc (const void * a, const void * b)
{
   return ( ((struct edge*)a)->c - ((struct edge*)b)->c );
}

//returns the root of tree where x lives
int find(int* parent, int x)
{   int r = x;

    while (parent[r])
        r = parent[r];
    // r is now the root
 
    while(x != r) {
        int aux = parent[x];
        parent[x] = r;
        x = aux;
    }
    
    return r;
}


void unite (int* parent, int* height, int x, int y)
{
    if(height[x] < height[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (height[x] == height[y])
            height[x]++;
    }
}

int main()
{
    int n, m, i, sum = 0;
    struct edge *edgs;
    int *parent, *height; 
    FILE *infile, *outfile;

    infile = fopen("apm.in", "r");
    outfile = fopen("apm.out", "w");
    
    fscanf(infile, "%d", &n);
    fscanf(infile, "%d", &m);
    
    parent = malloc((n+1) * sizeof(int));
    height = malloc((n+1) * sizeof(int));
    for (i = 1; i <= n; i++) {
        parent[i] = 0;
        height[i] = 1;
    }
    
    edgs = malloc(m * sizeof(struct edge));
    for (i = 0; i < m; i++) {
        fscanf(infile, "%d", &edgs[i].x);
        fscanf(infile, "%d", &edgs[i].y);
        fscanf(infile, "%d", &edgs[i].c);
        edgs[i].s = 0;
    }
    
    qsort(edgs, m, sizeof(struct edge), cmpfunc);
    for(i = 0; i < m; i++) {
        int rx, ry;
        rx = find(parent, edgs[i].x);
        ry = find(parent, edgs[i].y);
        if (rx != ry) {
            unite(parent, height, rx, ry);
            sum = sum + edgs[i].c;
            edgs[i].s = 1;
        }          
    }
    fprintf(outfile, "%d\n", sum);
    fprintf(outfile, "%d\n", n-1);
    for (i = 0; i < m; i++)
        if(edgs[i].s)
           fprintf(outfile, "%d %d\n", edgs[i].x, edgs[i].y);

 
    return 0;
}