#include <fstream>
#include <algorithm>

using namespace std;

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

int t[100020], rang[100021], cst, i, k, muci[2][400020];

struct muchie
{
    int st, dr, ct;
}v[400020];

bool comp(muchie a, muchie b)
{
    return a.ct<b.ct;
}

int radacina(int x)
{
    if(t[x]!=0)
    {
        int k=radacina(t[x]);
        t[x]=k;
        return k;
    }
    else return x;
}

void unire(int x, int y)
{
    int rx=radacina(x), ry=radacina(y);
    if(rx!=ry)
    {
        cst+=v[i].ct;
        muci[0][++k]=x;
        muci[1][k]=y;
        if(rang[rx]>rang[ry])
            t[ry]=rx;
        else
        {
            t[rx]=ry;
            if(rang[x]==rang[y])
                rang[y]++;
        }
    }
}

int main()
{
    int m ,n, x, y;
    in>>n>>m;
    for(i=1; i<=m; i++)
        in>>v[i].st>>v[i].dr>>v[i].ct;
    sort(v+1,v+m+1,comp);
    for(i=1; i<=m; i++)
        unire(v[i].st, v[i].dr);
    out<<cst<<'\n'<<k<<'\n';
    for(int j=1; j<=k; j++)
        out<<muci[0][j]<<" "<<muci[1][j]<<'\n';
    return 0;
}