#include <cstdio>
#include <cstring>
#include <cassert>

#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>

using namespace std;

typedef long long LL;
typedef vector<int>::iterator it;

const int oo = 0x3f3f3f3f;
const int MAX_N = 100005;
const int NIL = -1;

struct Edge {
    int x, y, c;

    Edge() {}

    Edge(const int x, const int y, const int c) {
        this->x = x; this->y = y; this->c = c;
    }

    bool operator< (const Edge &other) const {
        return c < other.c;
    }
};

vector<Edge> E, MST;
int N, Father[MAX_N], MSTCost;

int Find(int X) {
    if (Father[X] == NIL)
        return X;
    Father[X] = Find(Father[X]);
    return Father[X];
}

inline bool Merge(int X, int Y) {
    X = Find(X); Y = Find(Y);
    if (X == Y)
        return false;
    Father[Y] = X;
    return true;
}

void Kruskal() {
    memset(Father, NIL, sizeof(Father));
    sort(E.begin(), E.end());
    for (size_t i = 0; i < E.size(); ++i) {
        if (Merge(E[i].x, E[i].y)) {
            MST.push_back(E[i]);
            MSTCost += E[i].c;
        }
    }
}

void Solve() {
    Kruskal();
}

void Read() {
    assert(freopen("apm.in", "r", stdin));
    int M; assert(scanf("%d %d", &N, &M) == 2);
    for (; M > 0; --M) {
        int X, Y, C; assert(scanf("%d %d %d", &X, &Y, &C) == 3);
        E.push_back(Edge(X, Y, C));
    }
}

void Print() {
    assert(freopen("apm.out", "w", stdout));
    printf("%d\n%d\n", MSTCost, static_cast<int>(MST.size()));
    for (size_t i = 0; i < MST.size(); ++i)
        printf("%d %d\n", MST[i].x, MST[i].y);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}