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

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

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

#define VM vector<muchie>
#define VI vector<int>

VM muchii, APM;
VI repr;
int n, m;

bool cmp(muchie u1, muchie u2) {
    return u1.c < u2.c;
}

void Kruskal(int &nodAPM, int &cost) {
    for (int u = 0; u < muchii.size(); ++u) {
        if (repr[muchii[u].x] == 0) {
            repr[muchii[u].x] = muchii[u].x;
        }
        if (repr[muchii[u].y] == 0) {
            repr[muchii[u].y] = muchii[u].y;
        }
        if (repr[muchii[u].x] != repr[muchii[u].y]) { // trb reuniti subarborii
            int subA = repr[muchii[u].x],
                subB = repr[muchii[u].y];
            for (int i = 1; i <= n; ++i) {
                if (repr[i] == subB) {
                    repr[i] = subA;
                }
            }
            cost += muchii[u].c;
            ++nodAPM;
            APM.push_back(muchii[u]);
        }
    }
}

void printMuchii(VM muc) {
    for (auto e : muc) {
        fout << e.x << ' ' << e.y << '\n';
    }
}

int main() { 
    fin >> n >> m;
    repr = VI(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        muchie u;
        fin >> u.x >> u.y >> u.c;
        muchii.push_back(u);
    }

    sort(muchii.begin(), muchii.end(), cmp);
    int cost = 0, nodAPM = 0;
    Kruskal(nodAPM, cost);
    
    fout << cost << '\n' << nodAPM  << '\n';
    printMuchii(APM);
}