#include <fstream>
#include <algorithm>
#include <vector>
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;
vector < pair <int,int> > sol;

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;
            sol.push_back(make_pair(u[i].y,u[i].x));
            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();

    std::vector<int>::iterator p1;
    for(p1 = sol.begin(); p1 != sol.end(); p1++)
    g <<*p1.first<<' '<<*p1.second<<'\n';

g.close();
return 0;
}