#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5 + 5;
int repr[NMAX], depth[NMAX];

void init(){
    int i;
    for(i = 0; i < NMAX; ++i){
        depth[i] = 1;
        repr[i] = i;
    }
}

int getRepr(int a){
    if(repr[a] == a) return a;
    int ra = getRepr(repr[a]);
    repr[a] = ra;
    return ra;
}

void attach(int a, int b){
    int ra, rb;
    ra = getRepr(a);
    rb = getRepr(b);

    if(depth[ra] < depth[rb]){
        repr[ra] = rb;
    }
    else{
        repr[rb] = ra;
        if(depth[rb] == depth[ra]) ++depth[ra];
    }
}

bool sameTree(int a, int b){
    return getRepr(a) == getRepr(b);
}

struct edge{
    int a, b, c;
};

bool comp(edge A, edge B){
    return A.c < B.c;
}

vector <edge> g;

int main()
{
    int n, m, i, j;
    init();

    fin >> n >> m;
    for(i = 1; i <= m; ++i){
        int a, b, c;
        fin >> a >> b >> c;
        g.push_back({a, b, c});
    }



    sort(g.begin(), g.end(), comp);

    int sum = 0;
    vector < pair <int, int> > ans;
    for(auto &it: g){
        if(sameTree(it.a, it.b)) continue;

        sum += it.c;
        attach(it.a, it.b);
        ans.push_back({it.a, it.b});
    }

    fout << sum << '\n' << ans.size() << '\n';
    for(auto &it: ans)
        fout << it.first << ' ' << it.second << '\n';

    return 0;
}