#include <algorithm>
#include <climits>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

#define MAXN 200001
#define MAXM 400000

long long mincost = 0;
struct edge {
    int u;
    int v;
    long long w;
};

edge edges[MAXM];
int parent[MAXN];
int srank[MAXN];
vector<edge *> apm;

int n, m;

bool comp(const edge &e1, const edge &e2) { return e1.w < e2.w; }

int findSet(int u) {
    int root, temp;
    root = u;
    while (root != parent[root]) root = parent[root];

    while (u != parent[u]) {
        temp = parent[u];
        parent[u] = root;
        u = temp;
    }

    return root;
}

void unite(int u, int v) {
    int r1 = findSet(u);
    int r2 = findSet(v);

    if (srank[r1] > srank[r2]) {
        parent[r2] = r1;
    } else {
        parent[r1] = r2;
    }

    if (srank[r1] == srank[r2]) srank[r2]++;
}

int main() {
    // stuff

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

    fin >> n >> m;

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        srank[i] = 0;
    }

    for (int i = 0; i < m; i++) {
        fin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    sort(edges, edges + m, comp);

    for (int i = 0; i < m; i++) {
        if (findSet(edges[i].u) != findSet(edges[i].v)) {
            apm.push_back(&edges[i]);
            unite(edges[i].u, edges[i].v);
            mincost += edges[i].w;
        }
    }

    fout << mincost << '\n';
    fout << apm.size() << '\n';
    for (int i = 0; i < apm.size(); i++) {
        fout << apm[i]->v << " " << apm[i]->u << '\n';
    }

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

    return 0;
}