#include <fstream>
#include <algorithm>
#include <vector>

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

struct muchie{
    int x,y,c;
};
vector<muchie> m, v;
int n,nrm,s,rx,ry,t[110],i,j,cnt,k;

void citire()
{
    int i;
    muchie muc;

    fin>>n>>nrm;
    for(i=0; i<nrm; i++)
    {
        fin>>muc.x>>muc.y>>muc.c;
        m.push_back(muc);
    }
}

int radacina(int k)
{
    if(t[k]==k)
        return k;
    else
    {
        int r=radacina(t[k]);
        t[k]=r;
        return r;
    }
}

bool comp(muchie x, muchie y)
{
    return (x.c < y.c);
}

int main()
{
    citire();
    sort(m.begin(), m.end(), comp);

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

    s=cnt=0;
    for(i=0; i<nrm && cnt<n; i++)
    {
        rx=radacina(m[i].x);
        ry=radacina(m[i].y);
        if(rx!=ry)
        {
            s+=m[i].c;
            k++;
            v.push_back(m[i]);
            t[rx]=ry;
        }
    }

    fout<<s<<'\n'<<k<<'\n';
    for(auto muc : v)
    {
        fout<<muc.x<<" "<<muc.y<<'\n';
    }
    return 0;
}