#include <fstream>
#include <algorithm>

using namespace std;

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

int m,n,nr,x,y,sf,val,s,j;
struct {int e1,e2;} sol[200001];

struct muu{int e1,e2,c;};
muu v[400001];

int cc[200001];

bool cmp(muu v, muu w)
{
    if(v.c < w.c) return true;
    return false;
}


int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++) f >> v[i].e1 >> v[i].e2 >> v[i].c;

    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= n; i++) cc[i] = i;

    int i = 1;
    nr = 0;
    while(nr < n - 1)
    {
        x = v[i].e1;
        y = v[i].e2;
        if(cc[x] != cc[y])
        {
            sol[++sf].e1 = x;
            sol[sf].e2 = y;
            s += v[i].c;
            nr++;

            val = cc[y];
            for(j = 1; j <= n; j++)
                if(cc[j] == val)
                    cc[j] = cc[x];
        }
        i++;
    }

    g << s << "\n" << n - 1 << "\n";
    for(int i = 1; i < n; i++) g << sol[i].e1 << " " << sol[i].e2 << "\n";
    return 0;
}