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

using namespace std;

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

struct Muchie
{
    int x, y, cost;
};

const int NMAX = 200005;
const int MMAX = 400005;
int N, M, dad[NMAX], rang[NMAX];
Muchie m[MMAX];
vector < Muchie > apm;

void read() {
    fin >> N >> M;
    for (int i = 1; i <= M; i++) {
        fin >> m[i].x >> m[i].y >> m[i].cost;
    }
}

int root(int x) {
    if (dad[x] == 0)
        return x;
    else {
        int repr = root(dad[x]);
        dad[x] = repr;
        return repr;
    }
}

void unite(int x, int y) {
    int repr_x = root(x);
    int repr_y = root(y);
    if (repr_x != repr_y) {
        if (rang[repr_x] > rang[repr_y])
            dad[repr_y] = repr_x;
        else if (rang[repr_x] < rang[repr_y])
            dad[repr_x] = repr_y;
        else {
            dad[repr_y] = repr_x;
            rang[repr_x]++;
        }
    }
}

int find(int x, int y) {
    return(root(x) == root(y));
}

int main()
{
    int cost_total = 0;
    read();
    sort(m + 1, m + M + 1, [](Muchie m1, Muchie m2) {
        return m1.cost < m2.cost;
        });

    for (int i = 1; i <= M && apm.size() <= N - 1; i++) {
        if (!find(m[i].x, m[i].y)) {
            cost_total += m[i].cost;
            apm.push_back(m[i]);
            unite(m[i].x, m[i].y);
        }
    }

    fout << cost_total << "\n";
    fout << apm.size() << "\n";

    for (int i = 0; i < apm.size(); i++) {
        fout << apm[i].y << " " << apm[i].x << "\n";
    }
}