#include <iostream>
#include <fstream>
#define NMaxVf 50
#define NMaxMuchii NMaxVf * (NMaxVf - 1) / 2
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

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

muchie gr[NMaxMuchii];
int a[NMaxVf], c[NMaxVf];
int n, m, costAPM, nrM;

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> gr[i].x >> gr[i].y >> gr[i].cost;
    for (int i = 1; i <= n; i++)
        c[i] = i;
}

void show() {
    fout << costAPM << "\n" << nrM << "\n";
    for (int i = 1; i <= nrM; i++) {
        fout << gr[a[i]].y << " " << gr[a[i]].x << "\n";
        costAPM += gr[a[i]].cost;
    }
}

void sortMuchii(int st, int dr) {
    muchie t;
    int i, j;
    if (st < dr) {
        t = gr[st];
        i = st;
        j = dr;
        while (i < j) {
            while (i < j && gr[j].cost >= t.cost)
                j--;
            gr[i] = gr[j];
            while (i < j && gr[i].cost <= t.cost)
                i++;
            gr[j] = gr[i];
        }
        gr[i] = t;
        sortMuchii(st, i - 1);
        sortMuchii(i + 1, dr);
    }
}

int main() {
    int minim, maxim, nrMSel = 0;
    read();
    sortMuchii(1, m);
    for (int i = 1; nrMSel < n - 1; i++)
        if (c[gr[i].x] != c[gr[i].y]) {
            a[++nrMSel] = i;
            costAPM += gr[i].cost;
            nrM++;
            if (c[gr[i].x] < c[gr[i].y]) {
                minim = c[gr[i].x];
                maxim = c[gr[i].y];
            }
            else {
                minim = c[gr[i].y];
                maxim = c[gr[i].x];
            }
            for (int j = 1; j <= n; j++)
                if (c[j] == maxim)
                    c[j] = minim;
        }
    show();
}

/*
#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct muchies {
   int x, y, cost;
}v[NMAX], aux;
 
int viz[NMAX], n, m, c, nr;
vector<pair<int, int>> vec;
 
void citire() {
    int i;
    fin >> n;
    fin >> m;
    for(i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;
}

void sortare() {
    int k = 0, i;
    while(k == 0) {
        k = 1;
        for(i = 1; i < m; i++) {
            if(v[i].cost > v[i + 1].cost) {
                aux = v[i + 1];
                v[i + 1] = v[i];
                v[i] = aux;
                k = 0;
            }
        }
    }
}
 
void kruskal() {
    int i , j, k;
    i = 1;
    for(k = 1; k < n; k++) {
        while(viz[v[i].x] == viz[v[i].y] && viz[v[i].x] != 0)
            i++;
        c += v[i].cost;
        vec.push_back(make_pair(v[i].x, v[i].y));
        nr++;
        if(viz[v[i].x] + viz[v[i].y] == 0)
            viz[v[i].x] = viz[v[i].y] = v[i].x;
        else
            if(viz[v[i].x] * viz[v[i].y] == 0)
                viz[v[i].x] = viz[v[i].y] = viz[v[i].x] + viz[v[i].y];
            else {
                for(j = 1; j <= n; j++)
                    if(viz[j] == viz[v[i].x] && j != v[i].x)
                        viz[j] = viz[v[i].y];
                viz[v[i].x] = viz[v[i].y];
            }
        i++;
    }
    fout << c << "\n" << nr << "\n";
    for (int i = 0; i < vec.size(); i++)
        fout << vec[i].second << " " << vec[i].first << "\n";
}
 
int main()
{
    citire();
    sortare();
    kruskal();
}
*/