# include <fstream>
# include <algorithm>
# include <vector>
# include <queue>
# include <cstring>
# define LB(p) ((-p)&p)
# define NR 400005
# define mod 1999999973
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int i,j,n,m,x,y,tip,Rx,Ry,COST,nrsol;
int R[NR], H[NR];
struct elem
{
    int x, y, cost;
}a[NR],sol[NR];
bool cmp (elem x, elem y)
{
    if (x.cost>=y.cost) return 0;
                   else return 1;
}
int radacina (int k)
{
    while (k!=R[k]) k=R[k];
    return k;
}
void APM ()
{
    int i;
    for (i=1; i<=n; ++i)
        R[i]=i, H[i]=1;

    int muchii=0;
    for (i=1; i<=m && muchii<n; ++i)
    {
        Rx=radacina (a[i].x);
        Ry=radacina (a[i].y);
        if (Rx!=Ry) //reunire
        {
            COST+=a[i].cost; ++muchii;
            sol[++nrsol].x=a[i].x; sol[nrsol].y=a[i].y;
            if (H[Rx]>H[Ry]) R[Ry]=Rx, H[Rx]+=H[Ry];
                        else R[Rx]=Ry, H[Ry]+=H[Rx];
        }
    }
}
int main ()
{
    f>>n>>m;
    for (i=1; i<=m; ++i)
        f>>a[i].x>>a[i].y>>a[i].cost;

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

    APM ();
    g<<COST<<"\n";
    g<<nrsol<<"\n";
    for (i=1; i<=nrsol; ++i)
        g<<sol[i].x<<" "<<sol[i].y<<"\n";


    return 0;
}