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

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,maxi=0,mini=m;
    while( k <= n - 1 )
    {   if( l[u[i].x] != l[u[i].y] )
        {   k++;
            cost=cost+u[i].c;

            if( l[u[i].x] < l[u[i].y] ) {mini=l[u[i].x]; maxi=l[u[i].y];}
            else {mini=l[u[i].y]; maxi=l[u[i].x];}

            for(int j=1;j<=n;++j)
                if( l[j] == maxi ) l[j]=mini;
        }
        i++;
    }
    g<<cost<<'\n'<<k-1<<'\n';
}

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

            if( l[u[i].x] < l[u[i].y] ) {mini=l[u[i].x]; maxi=l[u[i].y];}
            else {mini=l[u[i].y]; maxi=l[u[i].x];}

            for(int j=1;j<=n;++j)
                if( l[j] == maxi ) l[j]=mini;
        }
        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();
    Initializare();
    Kruskal_2();

g.close();
return 0;
}