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

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

int T[1001], n, m, cnt, rez;

struct poz {
    int i, j, c;
} M[1001];

poz A[1001];

void leaga (int a, int b){
    T[a] = T[b];
}

int radacina (int a){
    if(a == T[a]) return a;
    else return T[a] = radacina(T[a]);
}

void kruskal()
{
    int r1, r2;
    for (int i = 1; i <= m; i++)
    {
        r1 = radacina(M[i].i), r2 = radacina(M[i].j);
        if(r1 != r2)
        {
            rez += M[i].c;
            A[++cnt] = M[i];
            leaga(r1, r2);
        }
    }
}

int comp (poz a, poz b){
    return a.c < b.c;
}

int main()
{
    in >> n >> m;
    for (int i = 1 ; i <= m ; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        M[i].i = x , M[i].j = y , M[i].c = cost;
    }

    sort (M + 1 , M + m + 1 , comp);

    for (int i = 1 ; i <= n ; i++) T[i] = i;

    kruskal();

    out << rez << "\n" << n-1 << "\n";

    for (int i = 1 ; i < n ; i++)
        out << A[i].i << " " << A[i].j << "\n";

    return 0;
}