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

using namespace std;

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

const int NMAX = 100;
const int MMAX = 100;

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

muchie v[MMAX];
int n, m, mat[MMAX][2];

bool sortare(muchie i, muchie j){
    return (i.cost < j.cost);
}

void kruskal()
{
    int l[100], k = 0, i = 1, s=0;
    for(int i = 1; i <= n; i++)
        l[i] = i;
    while(k < n-1){
        if(l[v[i].x] != l[v[i].y]){
            k++;
            s += v[i].cost;
            mat[k][0] = v[i].x;
            mat[k][1] = v[i].y;

            int a = l[v[i].y];
            int b = l[v[i].x];

            for(int j = 1; j <= n; j++)
                if(l[j] == a)
                    l[j] = b;
         }
         i++;
    }

    fout << s << "\n" << k << "\n";
    for(int i = 1; i <= k; i++)
        fout << mat[i][0] << " " << mat[i][1] << "\n";
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;

    sort(v+1, v+m+1, sortare);
    kruskal();

    return 0;
}