#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

vector<pair < int, pair<int, int>>> cost_muchie;
vector<pair<int,int>> sol;
int n,m,cost, tata[110000], dim[10000];

void init() {
    for (int i=1; i<=n; i++) {
        tata[i] = i;
        dim[i] = 1;
    }
}

int find(int x){
    while (x != tata[x]) {
        x = tata[x];
        find(x);
    }
    return x;
}

void uneste(int x, int y){
    int tataX = find(x);
    int tataY = find(y);

    if (dim[tataX] >= dim[tataY]) {
        tata[tataY] = tataX;
        dim[tataX] += dim[tataY];
    } else {
        tata[tataX] = tataY;
        dim[tataY] += dim[tataX];
    }
}

void kruskal()
{
    for (auto muchie : cost_muchie){
        int x = muchie.second.first;
        int y = muchie.second.second;
        if (find(x) != find(y)) {
            uneste(x,y);
            cost += muchie.first;
            sol.push_back(make_pair(x,y));
        }
    }

}

int main() {
    int x,y,costul;
    cin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        cin >> x >> y >> costul;
        cost_muchie.push_back(make_pair(costul, make_pair(x,y)));
    }

    init();
    sort(cost_muchie.begin(), cost_muchie.end());
    kruskal();
    cout << cost << "\n" << sol.size() << "\n";

    for (int i=0; i<sol.size(); i++)
    {
        cout << sol[i].first << " " << sol[i].second << "\n";
    }
    return 0;
}