#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
   int x,y,c;
}ST[400002];

struct APM
{
    int x,y;
}sol[200002];
int N,M,C,k,tata[200002];

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

int radacina(int xp)
{
     if( tata[xp] == 0 )
        return xp;
      tata[xp] = radacina( tata[xp] );

      return tata[xp];
}

int main()
{

    f>>N>>M;
    for(int i = 1 ; i <= M ; i++)
        f>>ST[i].x>>ST[i].y>>ST[i].c;

    sort(ST+1,ST+M+1,comp);

    int rx,ry;
    for(int i = 1 ; i <= M ; i++)
    {
        rx = radacina( ST[i].x );
        ry = radacina( ST[i].y );

        if( rx != ry )
        {
            C = C + ST[i].c;
            k++;
            sol[k].x = ST[i].x;
            sol[k].y = ST[i].y;

            tata[ ry ] = rx;
        }

        if( k == N-1 )
          break;
    }

    g<<C<<'\n'<<k<<'\n';
    for(int i = 1 ; i <= k ; i++)
    g<<sol[i].y<<' '<<sol[i].x<<'\n';

    return 0;
}