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

struct Edge {
    int a, b, cost;
};

bool cmp(Edge &e1, Edge &e2) {
    return e1.cost < e2.cost;
}

vector<int> parent, rank;

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void make_set(int v) {
    parent[v] = v;
    rank[v] = 0;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    int n, m;
    fin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        fin >> edges[i].a >> edges[i].b >> edges[i].cost;

    sort(edges.begin(), edges.end(), cmp);

    parent.resize(n + 1);
    rank.resize(n + 1);
    fill(rank.begin(), rank.end(), 0);
    for (int i = 1; i <= n; i++)
        make_set(i);

    int cost = 0;
    vector<pair<int, int>> result;
    for (Edge &e : edges) {
        if (find_set(e.a) != find_set(e.b)) {
            cost += e.cost;
            result.push_back({e.a, e.b});
            union_sets(e.a, e.b);
        }
    }

    fout << cost << '\n' << result.size() << '\n';
    for (auto &edge : result)
        fout << edge.first << ' ' << edge.second << '\n';

    fin.close();
    fout.close();

    return 0;
}