#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct Muchie {
    int x, y, cost;
};

int parent[200005];


int Find(int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}


void Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);
    parent[px] = py;
}


bool cmp(Muchie a, Muchie b) {
    return a.cost < b.cost;
}

int main() {
    int N, M;
    fin >> N >> M;
    
    vector<Muchie> E(M);
    
    for (int i = 0; i < M; i++) {
        fin >> E[i].x >> E[i].y >> E[i].cost;
    }
    
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
    
    sort(E.begin(), E.end(), cmp);
    
    vector<pair<int, int>> M_sol;
    int sol = 0;
    int cnt = 0;
    
    for (int i = 0; i < M; i++) {
        int x = E[i].x;
        int y = E[i].y;
        int c = E[i].cost;
        
        if (Find(x) != Find(y)) {
            sol += c;
            M_sol.push_back({x, y});
            Union(x, y);
            cnt++;
            
            if (cnt == N - 1) {
                break;
            }
        }
    }
    
    fout << sol << endl;
    fout << M_sol.size() << endl;
    for (auto muchie : M_sol) {
        fout << muchie.first << " " << muchie.second << endl;
    }
    
    return 0;
}