#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream o("apm.out");
#define size 20000
long int  key[size], V, M, graph[size][size], parent[size],sum;
bool mstSet[size];
int minKey() {
    // Initialize min value
    int min = INT_MAX, min_index;

    for (int v = 1; v <= V; v++)
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }

    return min_index;
}

void printMST() {
    for (int i = 2; i <= V; i++)
        sum+=graph[i][parent[i]];
    o << sum<<"\n"<<V-1<<"\n";
    for (int i = 2; i <= V; i++)
        o << parent[i] << " " << i << " \n";
}
void primMST() {
    // Array to store constructed MST

    for (int i = 1; i <=V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    key[1] = 0;
    parent[1] = -1;
    // First node is always root of MST
    for (int count = 1; count <= V; count++) {
        int u = minKey();
        mstSet[u] = true;
        for (int v = 1; v <= V; v++)
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
    }
    printMST();
}
int main() {
    f >> V >> M;
    int x,y,c;
    while(f>>x>>y>>c){
        graph[x][y]=c;
        graph[y][x]=c;
    }


    primMST();

    return 0;
}