#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define Nmax 1001

struct varf {int vf; varf* tata;} *v[Nmax];
struct muchie {int a, b, c;};
vector <muchie> M;
vector <int> h(Nmax);
vector< pair<int, int> > sol;
vector< pair<int, int> >::iterator it;


void read(int&, int&) ;
varf* find(int) ;
void uneste(varf*, varf*) ;
bool CMP(muchie, muchie) ;

int main()
{
    int i, n, m, s = 0;
    varf *v1, *v2;
    read(n, m);
    
    sort(M.begin(), M.end(), CMP);
    
    for(i = 1; i <= n; ++i)
    {
        v[i] = new varf;
        v[i] -> vf = i;
        v[i] -> tata = NULL;
    }
    
    for(i = 0; i < m; ++i)
    {
        v1 = find(M[i].a);
        v2 = find(M[i].b);
        if(v1 != v2)
            uneste(v1, v2),
            s += M[i].c,
            sol.push_back(make_pair(M[i].a, M[i].b));
    }
    fout << s << '\n' << n - 1 << '\n';
    for(it = sol.begin(); it != sol.end(); ++it)
        fout << (it -> first) << ' ' << (it -> second) << '\n';
    return 0;
}

void read(int &n, int &m)
{
    int i;
    muchie aux;
    fin >> n >> m;
    
    for(i = 0; i < m; ++i)
    {
        fin >> aux.a >> aux.b >> aux.c;
        M.push_back(aux);
    }
}


varf* find(int vf)
{
    varf *nod;
    for(nod = v[vf]; nod -> tata != NULL; nod = nod -> tata) ;
    return nod;
}


void uneste(varf* v1, varf* v2)
{
    if(h[v1 -> vf] < h[v2 -> vf])
    {
        v1 -> tata = v2;
        if(h[v2 -> vf] < 1 + h[v1 -> vf])
            h[v2 -> vf] = 1 + h[v1 -> vf];
        return;
    }
    
    v2 -> tata = v1;
    if(h[v1 -> vf] < 1 + h[v2 -> vf])
        h[v1 -> vf] = 1 + h[v2 -> vf];
    return;
}


bool CMP(muchie m1, muchie m2)
{
    return m1.c < m2.c;
}