#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 400005
#define NMAX 200005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct node {
    int x, y, cost;

    bool operator < (node a) const {
        return cost < a.cost;
    }
}edges[DIM];

int n, m, ans, t[NMAX];
vector <pair<int, int>> ansEdges;

int radacina(int a) {
    if (a == t[a])
        return a;
    return t[a] = radacina(t[a]);
}

void link(int a, int b, node edge) {
    ans += edge.cost;
    t[a] = t[b];
    ansEdges.push_back(make_pair(edge.x, edge.y));
}

void apm() {
    sort(edges + 1, edges + 1 + m);
    for (int i = 1; i <= m; i++) {
        int radX = radacina(edges[i].x);
        int radY = radacina(edges[i].y);
        if (radX != radY) {
            link(radX, radY, edges[i]);
        }
    }
}

int main() {

    f >> n >> m;

    for (int i = 1; i <= n; i++) {
        t[i] = i;
    }

    for (int i = 1; i <= m; i++) {
        f >> edges[i].x >> edges[i].y >> edges[i].cost;
    }

    apm();

    g << ans << "\n";
    g << ansEdges.size() << "\n";
    for (auto x: ansEdges) {
        g << x.first << " " << x.second << "\n";
    }

    return 0;
}