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

#define in "apm.in"
#define out "apm.out"
#define Max_Size 200009

typedef std :: pair < std :: pair < int, int >, int > ARC;

std :: ifstream f(in);
std :: ofstream g(out);

int N, M, P[Max_Size], Rank[Max_Size];
std :: vector < ARC > V, Arb;

class APM {
    public :
        void Init();
        int Find(int);
        void Union(int, int);
};

void APM :: Init() {
    for(int i = 1; i <= N; ++i) P[i] = i;
}

int APM :: Find(int node) {
    int Root;
    for(Root = node; Root != P[Root]; Root = P[Root]);
    for(int aux; node != P[node]; aux = P[node] , P[node] = aux, node = aux);

    return Root;
}

void APM :: Union(int node, int node1) {
    if(Rank[node] > Rank[node1])    P[node1] = node;
    if(Rank[node] < Rank[node1])    P[node] = node1;

    if(Rank[node] == Rank[node1])   {
        Rank[node1] ++;
        P[node1] = node;
    }
}

struct cmp {
    bool operator() (const ARC &a, const ARC &b) {
        if(a.second > b.second) return 0;
        return 1;
    }
};

int main() {
    f >> N >> M;

    APM obj; ARC xyc; int cost = 0;

    obj.Init();
    for(int i = 1; i <= M; ++i) {
        f >> xyc.first.first >> xyc.first.second >> xyc.second;
        V.push_back(xyc);
    }
    std :: sort(V.begin(), V.end(), cmp());
    for(int i = 0; i < M && Arb.size() < N - 1; ++i)
        if(obj.Find(V[i].first.first) != obj.Find(V[i].first.second))   {
            Arb.push_back(V[i]);
            obj.Union(obj.Find(V[i].first.first), obj.Find(V[i].first.second));
        }
    for(auto val : Arb) cost += val.second;

    g << cost << '\n' << Arb.size() << '\n';
    for(auto val : Arb)  g << val.first.first << ' ' << val.first.second << '\n';

    g.close();
    return 0;
}