#include    <fstream>
#include    <algorithm>

using namespace std;

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

#define ARRAY_MAX 400005

int Level[ARRAY_MAX], Parent[ARRAY_MAX];
int N, M, Total, cnt;

pair <int, int> P[ARRAY_MAX];

struct Container {
    int X, Y, Cost;
};

Container Edge[ARRAY_MAX];

bool Compare(Container X, Container Y) {
    if (X.Cost < Y.Cost)
        return true;

    return false;
}

void Read() {
    fin >> N >> M;

    for (int i = 1; i <= M; i++)
        fin >> Edge[i].X >> Edge[i].Y >> Edge[i].Cost;

    sort(Edge + 1, Edge + M + 1, Compare);

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

int Root(int K) {
    if (Parent[K] == K)
        return K;

    return Root(Parent[K]);
}

void Merge(int X, int Y) {
    if (Root(X) != Root(Y)) {
        if (Level[Root(X)] > Level[Root(Y)])
            Parent[Root(Y)] = Root(X);

        else {
            Parent[Root(X)] = Root(Y);

            if (Level[Root(X)] == Level[Root(Y)])
                Level[Root(Y)]++;
        }
    }
}

void Solve() {
    for (int i = 1; i <= M; i++) {
        if (Root(Edge[i].X) != Root(Edge[i].Y)) {
            Merge(Root(Edge[i].X), Root(Edge[i].Y));

            P[++cnt].first = Edge[i].X;
            P[cnt].second = Edge[i].Y;

            Total += Edge[i].Cost;
        }
    }
}

void Write() {
    fout << Total << "\n";
    fout << N - 1 << "\n";

    for (int i = 1; i <= N - 1; i++)
        fout << P[i].second << " " << P[i].first << "\n";
}

int main() {
    Read();
    Solve();
    Write();
}