#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("Andrei.in"); ofstream g("Andrei.out");
int n,m,l[200010];
struct muchii {short x,y,c;}u[400010];
int cost,nrmuchiicostminim;

bool comp(muchii a,muchii b)
{   return a.c < b.c;
}

void Initializare()
{   for(int i=1;i<=n;++i) l[i]=i;
}

void Kruskal_1()
{   int k=1,i=1;
    while( k <= n - 1 )
    {   if( l[u[i].x] != l[u[i].y] )
        {   k++;
            cost+=u[i].c; nrmuchiicostminim++;
            for(int j=1;j<=n;++j)
                if( l[j] == l[u[i].y] ) l[j]=l[u[i].x];
        }
        i++;
    }
}

void Kruskal_2()
{   int k=1,i=1;
    while( k <= n - 1 )
    {   if( l[u[i].x] != l[u[i].y] )
        {   k++;
            g<<u[i].x<<" "<<u[i].y<<'\n';
            for(int j=1;j<=n;++j)
                if( l[j] == l[u[i].y] ) l[j]=l[u[i].x];
        }
        i++;
    }
}

int main()
{   f>>n>>m; for(int i=1;i<=m;++i) f>>u[i].x>>u[i].y>>u[i].c;
    sort(u+1,u+m+1,comp);
    Initializare();
    Kruskal_1();
    g<<cost<<'\n'<<nrmuchiicostminim<<'\n';
    Initializare();
    Kruskal_2();

g.close();
return 0;
}