#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int Nmax = 200005;
const int Mmax = 400005;

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

int father[Nmax], n, m, cost;
vector<int> sol;
Muchie v[Mmax];

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

int Find_root(int x) {
    if(father[x] < 0) {
        return x;
    }
    int root = Find_root(father[x]);
    father[x] = root;
    return root;
}

void Union(int x, int y) {
    int r_x = Find_root(x);
    int r_y = Find_root(y);
    if(r_x == r_y) {
        return;
    }
    if(father[r_x] < father[r_y]) {
        swap(r_x, r_y);
    }
    father[r_y] += father[r_x];
    father[r_x] = r_y;
}

bool isValid(int x, int y){
    if(Find_root(x) == Find_root(y)){
        return 0;
    }
    return 1;
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    fin >> n >> m;

    for(int i = 1; i <= n; i++){
        father[i] = -1;
    }

    for(int i = 0; i < m; i++){
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }

    sort(v, v + m, cmp);

    cost = 0;
    for(int i = 0; i < m; i++){
        if(isValid(v[i].x, v[i].y)){
            cost += v[i].cost;
            sol.push_back(i);
            Union(v[i].x, v[i].y);
        }
    }

    fout << cost << '\n';
    fout << sol.size() << '\n';
    for(int i : sol){
        fout << v[i].x << " " << v[i].y << '\n';
    }

    return 0;
}