#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {
    int x, y, w;
    bool used;
};
bool comp (muchie a, muchie b) {
    return a.w < b.w;
}
vector <muchie> v;
vector <int> apm;
int n, m, cost;
int main()
{
    fin>>n>>m;
    muchie t;
    for (int i = 1; i <=m; i++) {
        fin>>t.x>>t.y>>t.w;
        t.used = false;
        v.push_back(t);
    }
    apm.push_back(0);
    for (int i = 1; i <= n; i++) {
        apm.push_back(i);
    }
    sort(v.begin(), v.end(), comp);
    for (int i = 0; i < m; i++) {
        if (apm[v[i].x] != apm[v[i].y]) {
            cost = cost + v[i].w;
            v[i].used = true;
            int aux = apm[v[i].y];
            for (int j = 1; j <= n; j++) {
                if (apm[j] == aux) {
                    apm[j] = apm[v[i].x];
                }
            }
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for (int i = 0; i < m; i++) {
        if (v[i].used == true) {
            fout<<v[i].y<<' '<<v[i].x<<'\n';
        }
    }
    /*
    for (int i = 0; i < m; i++) {
        fout<<v[i].x<<' '<<v[i].y<<' '<<v[i].w<<'\n';
    }
    */
    return 0;
}