#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

bool compare(Muchie &m1, Muchie &m2) {
    return m1.cost < m2.cost;
}

int Find(int x, vector<int> &tata) {
    while (tata[x] != 0) {
        x = tata[x];
    }
    return x;
}

void Union(int x, int y, vector<int> &tata, vector<int> &h) {
    x = Find(x, tata);
    y=Find(y, tata);
    if (h[x] < h[y]) {
        tata[x]=y;
    }
    else {
        tata[y]=x;
        if (h[x] == h[y]) {
            h[y]++;
        }
    }
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, x, y, c, sol=0, nr=0;
    vector<Muchie> L, M;

    fin>>n>>m;
    for (int i=0; i< m; i++) {
        fin>>x>>y>>c;
        L.push_back(Muchie(x,y,c));
    }
    sort(L.begin(), L.end(), compare);
    vector<int> tata(n+1, 0), h(n+1, 1);

    for (const auto muchie : L) {
        if (Find(muchie.x, tata) != Find(muchie.y, tata)) {
            M.push_back(muchie);
            sol+=muchie.cost;
            Union(muchie.x, muchie.y, tata, h);
            nr++;
        }
    }
    fout<<sol<<"\n";
    fout<<nr<<"\n";
    for (const auto m : M) {
        fout<<m.x<<" "<<m.y<<"\n";
    }

    return 0;
}