#include<fstream>
#include<algorithm>
#define MMAX 400010
#define NMAX 200010

using namespace std;

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

struct muchie
{
    int x, y, c, vz;
}a[MMAX];

int n, m, T[NMAX], H[NMAX];

int cmp(muchie A, muchie B)
{
    return A.c<B.c;
}

void Citeste()
{
    int i;

    f>>n>>m;

    for (i=1; i<=m; ++i) f>>a[i].x>>a[i].y>>a[i].c;

    sort(a+1, a+m+1, cmp);
}

int tata(int nod)
{
    if (T[nod]==-1) return nod;
    return tata(T[nod]);
}

void Unifica(int x, int y)
{
    int tx=tata(x), ty=tata(y);

    if (H[tx]<H[ty]) T[tx]=ty;
    else
        if (H[ty]<H[tx]) T[ty]=tx;
            else
            {
                H[ty]++;
                T[tx]=ty;
            }
}

void Solve()
{
    int i, valapm=0;

    for (i=1; i<=n; ++i)
    {
        H[i]=1;
        T[i]=-1;
    }

    for (i=1; i<=m; ++i)
        if (tata(a[i].x)!=tata(a[i].y))
        {
            valapm+=a[i].c;
            a[i].vz=1;

            Unifica(a[i].x, a[i].y);
        }

    g<<valapm<<"\n"<<n-1<<"\n";

    for (i=1; i<=m; ++i)
        if (a[i].vz) g<<a[i].x<<" "<<a[i].y<<"\n";
}

int main()
{
    Citeste();

    Solve();

    f.close();
    g.close();

    return 0;
}