#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct edge {
    int weight, start_node, end_node;
};

int n, m, father[200001];
long long cost_minim;
vector<int> apm;
vector<edge> edges;

void citire();
void afisare();
void Kruskal();
int get_root(int x);
bool compare(edge a, edge b);


int main() {

    citire();
    Kruskal();
    afisare();

    return 0;
}

void Kruskal() {
    sort(edges.begin(), edges.end(), compare);
    for (int i = 1; i <= n; ++i) father[i] = i;

    for (int i = 0; i < m; ++i) {
        int root_a = get_root(edges[i].start_node);
        int root_b = get_root(edges[i].end_node);
        if (root_a == root_b) continue;

        father[root_a] = father[root_b];
        cost_minim += edges[i].weight;
        apm.push_back(i);
    }
}

int get_root(int x) {
    if (father[x] == x) return x;
    father[x] = get_root(father[x]);
    return father[x];
}

bool compare(edge a, edge b) {
    return a.weight < b.weight;
}

void afisare() {
    ofstream out("apm.out");

    out << cost_minim << '\n';
    out << apm.size() << '\n';

    for (int i = 0; i < apm.size(); ++i) {
        out << edges[apm[i]].start_node << " " << edges[apm[i]].end_node << '\n';
    }

    out.close();
}

void citire() {
    ifstream in("apm.in");
    int x, y, c;
    edge e;

    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> x >> y >> c;
        e.weight = c;
        e.start_node = x;
        e.end_node = y;
        edges.push_back(e);
    }

    in.close();
}