#include <stdio.h>
#include <utility>
#include <algorithm>
#include <vector>

#define MAX_NODES 100000

std::vector<int> mst[MAX_NODES + 1];
std::vector<std::pair<int, std::pair<int, int> > > graph;
int root[MAX_NODES + 1];
int size[MAX_NODES + 1];

bool cmp(std::pair<int, std::pair<int, int> > a,
         std::pair<int, std::pair<int, int> > b) {
    return a.first < b.first;
}

int get_root(int node) {
    while (node != root[node]) {
        root[node] = root[root[node]];
        node = root[node];
    }
    return node;
}
 
int find(int p, int q) {
    return get_root(p) == get_root(q);
}

void unite(int p, int q) {
    int i = get_root(p);
    int j = get_root(q);

    if (size[i] < size[j]) {
        root[i] = j;
        size[j] += size[i];
    } else {
        root[j] = i;
        size[i] += size[j];
    }
}

long long kruskal(int num_nodes) {
    int u, v, c;
    long long cost = 0;
    std::pair<int, std::pair<int, int> > m;
    
    for (int i = 1; i <= num_nodes; i++) {
        root[i] = i;
        size[i] = 1;
    }
    
    sort(graph.begin(), graph.end(), cmp);
    
    for (int i = 0; i < graph.size(); i++) {
        m = graph[i];
        u = m.second.first;
        v = m.second.second;
        c = m.first;
        
        if (!find(u, v)) {            
            mst[u].push_back(v);
            mst[v].push_back(u);
            
            unite(u, v);
            
            cost += c;
        }
    }
    
    return cost;
}

int main(void) {
    FILE * fin = fopen("apm.in", "r");
    FILE * fout = fopen("apm.out", "w");
    
    int n, m, u, v, c;
    
    fscanf(fin, "%d%d", &n, &m);
    
    for (int i = 0; i < m; i++) {
        fscanf(fin, "%d%d%d", &u, &v, &c);
        graph.push_back(std::make_pair(c, std::make_pair(u, v)));
    }
    
    fprintf(fout, "%d\n", kruskal(n));
    fprintf(fout, "%d\n", n - 1);
    for (int i = 1; i <= n; i++) {
        for (auto &adj_node : mst[i]) {
            if (i < adj_node) {
                fprintf(fout, "%d %d\n", i, adj_node); 
            }            
        }
    }
    
    fclose(fin);
    fclose(fout);
}