#include <bits/stdc++.h>

struct edge_data {
    edge_data (int x = 0, int y = 0, int weight = 0) {
        this->x = x;
        this->y = y;
        this->weight = weight;
    }   int x, y, weight;
    bool operator < (const edge_data& other) const {
        return weight < other.weight;
    }
};

#define MAXN 200005
#define MAXM 400005

int N, M,
    Sum;
std::vector <int> MSTIdx;
std::vector <edge_data> Edges;

inline void AddEdge(int x, int y, int w) {
    Edges.push_back({x, y, w});
}

int Root[MAXN],
    Rang[MAXN];

int Find(int X) {
    int r = X;
    while (Root[r] != r)
        r = Root[r];

    int Aux;
    while (Root[X] != X)
        Aux = Root[X],
        Root[X] = r,
        X = Aux;
    return r;
}

void Union(int X, int Y) {
    if (X == Y) return;

    if (Rang[X] == Rang[Y]) {
        Root[Y] = X;
        ++ Rang[X];
    }   else
    if (Rang[Y] < Rang[X]) {
        Root[Y] = X;
    }
    else {
        Root[X] = Y;
    }
}

void Kruskal() {
    int idx = 0,
        x, y;

    for (int i=1; i<=N; ++i)
        Root[i] = i;

    while (MSTIdx.size() < N-1) {
        x = Find(Edges[idx].x);
        y = Find(Edges[idx].y);

        if (x != y)
            MSTIdx.push_back(idx),
            Sum += Edges[idx].weight,
            Union(x, y);
        ++ idx;
    }
}

std::ifstream In("apm.in");
std::ofstream Out("apm.out");

void Citire() {
    In >> N >> M;
    for (int i=0, x, y, w; i<M; ++i)
        In >> x >> y >> w, AddEdge(x, y, w);
}

void Rezolvare() {
    std::sort(Edges.begin(), Edges.end());
    Kruskal();

    Out << Sum << '\n' << N-1 << '\n';
    for (int i=0; i<MSTIdx.size(); ++i)
        Out << Edges[MSTIdx[i]].x << ' ' << Edges[MSTIdx[i]].y << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}