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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

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

void citire(int &n, int &m, vector <muchie> &M) {
    int i, x, y, c;
    f >> n >> m;
    for(i = 1; i <= m; i++) {
        f >> x >> y >> c;
        muchie m;
        m.x = x;
        m.y = y;
        m.cost = c;
        M.push_back(m);
    }
}

int cmp(muchie m1, muchie m2) {
    if(m1.cost > m2.cost) return 0;
    return 1;
}

void afis(int c, vector <pair <int,int> > APCM) {
    int i;
    /*g << "Cost: " << c << '\n';
    g << "Muchii:" << '\n';
    for(i = 0; i < APCM.size(); i++) g << APCM[i].first << " " << APCM[i].second << '\n';*/
    g<<c<<'\n'<<APCM.size()<<'\n';
    for(i = 0; i < APCM.size(); i++) g << APCM[i].first << " " << APCM[i].second << '\n';

}

void kruskal(int n, int m, vector <muchie> M) {
    int T[1000] = {0}, H[1000] = {0}, i, x, y, c = 0, p1, p2;
    vector <pair <int,int> > APCM;
    for(i = 0; i < m; i++) {
        x = M[i].x;
        y = M[i].y;
        p1 = x;
        p2 = y;
        while(T[x] != 0) x = T[x];
        while(T[y] != 0) y = T[y];
        if(x != y) {
            APCM.push_back(make_pair(p1, p2));
            c += M[i].cost;
            if(H[x] >= H[y]) {
                T[y] = x;
                if(H[x] == H[y]) H[x]++;
            }
            else T[x] = y;
        }
    }
    afis(c, APCM);
}

int main()
{
    int n, m, i;
    vector <muchie> M;
    citire(n, m, M);
    sort(M.begin(), M.end(), cmp);
    kruskal(n, m, M);
    return 0;
}