#include <cstdio>
#include <vector>
#include <queue>

#define NMAX 200005

using namespace std;

int N, M, parent[NMAX], cost;
vector <pair <int, int> > graph[NMAX], apm[NMAX], ans;
priority_queue <pair <int, pair <int, int> > > edges;

void read() {
    int x, y, c;

    scanf("%d %d", &N, &M);

    for (int i = 1; i <= M; ++i) {
        scanf("%d %d %d", &x, &y, &c);
        graph[x].push_back(make_pair(c, y));
        edges.push(make_pair(-c, make_pair(x, y)));
    }

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

int findParent(int node) {
    if (node != parent[node]) {
        parent[node] = findParent(parent[node]);
    }
    return parent[node];
}

void kruskal() {
    int noEdges = 0, x, y, c, px, py;

    while (!edges.empty() && noEdges < N - 1) {
        c = edges.top().first;
        x = edges.top().second.first;
        y = edges.top().second.second;
        edges.pop();

        px = findParent(x);
        py = findParent(y);

        if (px != py) {
            parent[py] = px;
            ans.push_back(make_pair(x, y));
            cost += c;
        }
    }
}

void print() {
    printf("%d\n%d\n", -cost, N - 1);

    for (vector <pair <int, int> > :: iterator it = ans.begin(); it != ans.end(); ++it) {
        printf("%d %d\n", it -> first, it -> second);
    }
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    read();
    kruskal();
    print();
}