#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int kMaxN = 200005;
const int kMaxE = 400005;

struct Edge {
    int x, y, c;

    inline bool operator() (const Edge &a, const Edge &b) {
        return a.c < b.c;
    }
};

Edge E[kMaxE];
int N, NE, F[kMaxN], S;
vector <int> SE;

inline int Find(int X) {
    int Root = X;
    for (; F[Root]; Root = F[Root]);
    for (int Y; X != Root; Y = F[X], F[X] = Root, X = Y);
    return Root;
}

inline bool Merge(int X, int Y) {
    X = Find(X), Y = Find(Y);
    if (X != Y)
        F[X] = Y;
    return (X != Y);
}

void Kruskal() {
    sort(E, E+NE, Edge());
    for (int i = 0; i<NE; ++i) {
        int X = E[i].x, Y = E[i].y, C = E[i].c;
        if (Merge(X, Y))
            S += C, SE.push_back(i);
    }
}

void Read() {
    freopen ("apm.in", "r", stdin);
    scanf ("%d %d", &N, &NE);
    for (int i=0; i<NE; ++i)
        scanf ("%d %d %d", &E[i].x, &E[i].y, &E[i].c);
}

void Print() {
    freopen("apm.out", "w", stdout);
    printf("%d\n%d\n", S, N-1);
    for (; !SE.empty(); SE.pop_back())
        printf ("%d %d\n", E[SE.back ()].x, E[SE.back ()].y);
}

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