#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();



   for(int i = 0; i < sol.size(); ++i)
        g << sol[i].first << " " << sol[i].second << '\n';



g.close();

return 0;

}