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

FILE *input = fopen("apm.in","r");
FILE *output = fopen("apm.out","w");

int minKey(int key[], bool mstSet[], int n)
{
    int min = INT32_MAX, min_index;

    for (int v = 0; v < n; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

int printMST(int parent[], int n, int **graph)
{
    int s = 0;
    int count = 0;

    for (int i = 1; i < n; i++) {
        s += graph[i][parent[i]];
        count++;
    }

    fprintf(output,"%d\n%d\n",s,count);

    for (int i = 1; i < n; i++) {
        fprintf(output,"%d %d\n", parent[i] + 1, i + 1);
    }
}

void primMST(int **graph, int n)
{
    int parent[n];
    int key[n];
    bool mstSet[n];

    for (int i = 0; i < n; i++)
        key[i] = INT32_MAX, mstSet[i] = false;

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < n-1; count++)
    {
        int u = minKey(key, mstSet, n);
        mstSet[u] = true;
        for (int v = 0; v < n; v++)
            if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
                parent[v]  = u, key[v] = graph[u][v];
    }

    printMST(parent, n, graph);
}

int main() {
    int nodes,edges;
    int **graph;

    fscanf(input,"%d %d",&nodes,&edges);

    graph = (int**)malloc(nodes * sizeof(int*));
    for(int i = 0; i < nodes; i++) {
        graph[i] = (int*)malloc(nodes * sizeof(int));
    }

    for(int i =0; i < nodes; i++) {
        for(int j = 0; j < nodes; j++) {
            graph[i][j] = 0;
        }
    }

    for(int i = 0; i < edges; i++) {
        int x,y,cost;
        fscanf(input,"%d %d %d",&x,&y,&cost);
        graph[x - 1][y - 1] = cost;
        graph[y - 1][x - 1] = cost;
    }

    primMST(graph,nodes);

    return 0;
}