#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

#define NUME "apm"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
#define MAXN 200001
#define MAXM 400001
#define ve vector<edge>

int N, M;
//struct item { int x, c; item *r; } *L[MAXN];
int T[MAXN], rang[MAXN];
struct edge {
    int a, b, c;
    bool operator<(const edge &B) const {
        return c < B.c;
    }
};

ve Edges, Keep;
/*
void add(int a, int b, int c) {
    item *p = new item;
    *p = (item) { b, c, L[a] };
    L[a] = p;
}
*/
int multime(int i) {
    if (T[i] != T[T[i]])
        T[i] = multime(T[i]);
    return T[i];
}

void reunite(int a, int b) {
     if (rang[a] < rang[b])
         T[a] = b;
     else
         T[b] = a;
}

void kruskal() {
    int i, cost = 0;
    Keep.reserve(N-1);
    // initializam multimile
    for (i = 0; i < N; ++i)
        T[i] = i, rang[i] = 1;
    for (ve::iterator it = Edges.begin(); it != Edges.end(); ++it) {
        int a = it->a, b = it->b, c = it->c;
        a = multime(a);
        b = multime(b);
        if (a == b) continue;
        reunite(a, b);
        cost += c;
        Keep.push_back(*it);
    }
    fo << cost << "\n" << N-1 << "\n";
    for (ve::iterator it = Keep.begin(); it != Keep.end(); ++it) {
        fo << it->a << " " << it->b << "\n";
    }
}

int main()
{
    int i;
    fi >> N >> M;
    Edges.reserve(M);
    for (i = 0; i < M; ++i) {
        edge x;
        fi >> x.a >> x.b >> x.c;
        Edges.push_back(x);
    }
    sort(Edges.begin(), Edges.end());
    kruskal();
    return 0;
}