#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2e5;

struct Edge {
    int node1, node2;
    int cost;
};

vector<Edge> edges;
vector<Edge> apm;
int costApm;

int root[NMAX];
int height[NMAX];

int find(int x) {
    if(root[x] == x)
        return x;
    return (root[x] = find(root[x]));
}

bool sameRoot(int a, int b) {
    return find(a) == find(b);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if(a == b)
        return;
    if(height[a] < height[b])
        swap(a, b);
    root[b] = a;
    if(height[a] == height[b])
        height[a]++;
}


int main() {
    int n, m;
    FILE *fin, *fout;
    fin = fopen("apm.in", "r");
    fout = fopen("apm.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        int a, b, c;
        fscanf(fin, "%d%d%d", &a, &b, &c);
        edges.push_back({a, b, c});
    }
    for(int i = 0; i < n; i++)
        root[i] = i, height[i] = 1;
    sort(edges.begin(), edges.end(), [](Edge x, Edge y) {return x.cost < y.cost;});
    costApm = 0;
    for(auto e : edges) {
        if(!sameRoot(e.node1, e.node2)) {
            merge(e.node1, e.node2);
            costApm += e.cost;
            apm.push_back(e);
        }
    }
    fprintf(fout, "%d\n%d\n", costApm, apm.size());
    for(auto e : apm) {
        fprintf(fout, "%d %d\n", e.node1, e.node2);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}