#include <iostream>
#include <fstream>
#include <vector>
#define nmax 200005
#define swap(a,b) temp=a, a=b, b=temp;
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n, m, temp, viz[nmax];
struct graf
{
    int x, y, cost;

} v[nmax];

vector< pair<int,int> > sol;

void citeste()
{ int x, y;

    in>>n>>m;
    for (int i=1; i<=m; ++i)
     {
         in>>v[i].x>>v[i].y>>v[i].cost;
     }
}

void sort(int p_in, int p_sf)
{ int a, b, mij;

    a = p_in; b = p_sf;
    mij = (a+b) / 2;

    do
     {
         while ( v[a].cost < v[mij].cost ) ++a;
         while ( v[b].cost > v[mij].cost ) --b;
          if ( a <= b )
           {
               swap(v[a].x, v[b].x);
               swap(v[a].y, v[b].y);
               swap(v[a].cost, v[b].cost);
               ++a;
               --b;
           }
     } while ( a < b);

    if ( a < p_sf ) sort(a, p_sf);
    if ( b > p_in ) sort(p_in, b);
}

void kruskal()
{ int i = 1, costarb = 0;

    for (int k=1; k<n; ++k)
     {
         while ( viz[ v[i].x ] == viz[ v[i].y ] && viz[ v[i].x ] != 0 )
          ++i;

         costarb += v[i].cost;
         sol.push_back( make_pair( v[i].y, v[i].x ) );

         if ( viz[ v[i].x ] + viz[ v[i].y ] == 0 )
          viz[ v[i].x ] = viz[ v[i].y ] = v[i].x;

          else
           if ( viz[ v[i].x ] * viz[ v[i].y ] == 0 )
            viz[ v[i].x ] = viz[ v[i].y ] = viz[ v[i].x ] + viz[ v[i].y ];

          else
           {
               for ( int j=1; j<=n; ++j )
                if ( viz[j] == viz[ v[i].x ] && j != v[i].x )
                 viz[j] = viz[ v[i].y ];

               viz[ v[i].x ] = viz[ v[i].y ];
            }
        ++i;
     }

    out<<costarb<<'\n'<<sol.size()<<'\n';
    for (unsigned i = 0; i < sol.size(); ++i)
     out<<sol[i].first<<" "<<sol[i].second<<'\n';
}

int main()
{
    citeste();
    sort(1,m);
    sort(1,m);

    kruskal();
}