#include <fstream>
#include <queue>
using namespace std;

struct Edge {
    int n1, n2, cost;
    Edge(int x, int y, int c) {
        n1 = x;
        n2 = y;
        cost = c;
    }
    friend bool operator < (Edge e1, Edge e2) {
        return e2.cost < e1.cost;
    }
};

int Find(int x, int Rep[]) {
    int RepX = x, temp;
    while(RepX != Rep[RepX])
        RepX = Rep[RepX];
    while(x != Rep[x]) {
        temp = Rep[x];
        Rep[x] = RepX;
        x = temp;
    }
    return RepX;
}

void Union(int x, int y, int Rep[], int Rank[]) {
    int RepX = Find(x, Rep), RepY = Find(y, Rep);
    if(RepX > RepY) {
        Rep[RepY] = RepX;
        ++Rank[RepX];
    }
    else {
        Rep[RepX] = RepY;
        ++Rank[RepY];
    }
}

int n, m, Rep[200001], Rank[200001] {}, FinalCost = 0, i, x, y, c;
priority_queue<Edge> pq;
vector<pair<int, int>> Sol(200000);

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, Rep[200001], Rank[200001] {}, FinalCost = 0, i, x, y, c;
    priority_queue<Edge> pq;
    vector<pair<int, int>> Sol(200000);
    Edge current(1,1,1);
    fin >> n >> m;
    for(i = 1; i <= n; ++i)
        Rep[i] = i;
    for(i = 1; i <= m; ++i) {
        fin >> x >> y >> c;
        pq.push(Edge(x, y, c));
    }
    for(i = 1; i <= n-1; ++i) {
        do {
            current = pq.top();
            pq.pop();
        } while(Find(current.n1, Rep) == Find(current.n2, Rep));
        Sol[i] = {current.n1, current.n2};
        FinalCost += current.cost;
        Union(current.n1, current.n2, Rep, Rank);
    }
    fout << FinalCost << '\n' << n-1 << '\n';
    for(i = 1; i <= n-1; ++i)
        fout << Sol[i].first << ' ' << Sol[i].second << '\n';
}