#include <iostream>
#include <fstream>
#include <queue>
#include <functional>
#define NMax 200001
#define MMax 400001
using namespace std;

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

struct muchie {
    int x, y, c;

    friend bool operator> (muchie a, muchie b);
};

bool operator> (muchie a, muchie b) {
    return a.c > b.c;
}

priority_queue < muchie, vector<muchie>, greater<muchie> > H;
vector <muchie> A;  ///   APM
int cmin;           ///   COST APM
int n, m;
int tata[NMax];
int h[NMax];        /// h[i] = inaltimea arborelui de radacina i

int Find(int x) {
    int rad = x, y;

    while (tata[rad]) rad = tata[rad];

    /// COMPRESIA DRUMURILOR
    if (rad != x) {
        y = tata[x];
        while (y != rad) {
            tata[x] = rad;
            x = y;
            y = tata[x];
        }
    }

    return rad;
}

void Union(int x, int y) {
    int i = Find(x);
    int j = Find(y);

    if (i != j) {
        if (h[i] < h[j]) tata[i] = j;
        else
            if (h[i] > h[j]) tata[j] = i;
            else {
                tata[i] = j;
                h[j]++;
            }
    }
}

void citire();
void kruskal();
void afisare();

int main() {
    citire();
    kruskal();
    afisare();

    return 0;
}

void citire () {
    muchie aux;

    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        fin >> aux.x >> aux.y >> aux.c;
        H.push(aux);
    }
}

void kruskal() {
    muchie aux;
    int i, j;

    while (A.size() < n - 1) {
        aux = H.top();
        H.pop();

        i = Find(aux.x);
        j = Find(aux.y);

        if (i != j) {
            A.push_back(aux);
            cmin += aux.c;
            Union(i, j);
        }
    }
}

void afisare() {
    fout << cmin << '\n' << n - 1 << '\n';

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