//kruskal
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct muchie{
    int a,b,cost;
};
bool compara(muchie a, muchie b) {
    return a.cost < b.cost;
}
vector<muchie> M;
vector<muchie> tree;
int n,m,nrnod=0,suma=0;
int tata[200001], h[200001];
void init(int u){tata[u] = h[u] = 0;}
int reprez(int u) {
    while (tata[u]) u = tata[u];
    return u;
}
void reuneste(int u, int v) {
    int ru,rv;
    ru = reprez(u);
    rv = reprez(v);
    if (h[ru] > h[rv])
        tata[rv]=ru;
    else {
        tata[ru] = rv;
        if (h[ru] == h[rv]) h[rv]++;
    }
}
int main() {
    fin>>n>>m;
    M.resize(m+1);
    for (int i=1;i<=m;i++) {
        fin>>M[i].a>>M[i].b>>M[i].cost;
    }

    sort(M.begin()+1,M.end(),compara);
    for ( auto x : M) {
        if (reprez(x.a) != reprez(x.b)) {
            tree.push_back(x);
            reuneste(x.a, x.b);
            nrnod++;
            suma+=x.cost;
            if (nrnod == n-1)
                break;
        }
    }
    fout<<suma<<'\n'<<nrnod<<'\n';
    for (int i=0;i<nrnod;i++)
        fout<<tree[i].b<<' '<<tree[i].a<<'\n';

    return 0;
}