#include <fstream>
#include <cstdlib>
using namespace std;

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

int m,n,i,j,a[200001];
int k,val,r[400001],rc;

struct mk{int x,y,z;};
mk v[400001];

 int compare_ints( const void* a, const void* b ) {
     mk* arg1 = (mk*) a;
     mk* arg2 = (mk*) b;
     if( (*arg1).z < (*arg2).z ) return -1;
     else if( (*arg1).z == (*arg2).z ) return 0;
     else return 1;
   }


int main()
{
    f>>n>>m;
    for(i=0;i<m;i++) f>>v[i].x>>v[i].y>>v[i].z;
    for(i=1;i<=n;i++) a[i]=i;

    qsort( v, m, sizeof(mk), compare_ints );

    for(i=0;i<m;i++)
    {
        while(v[i].z==0) i++;

        if(a[v[i].x]!=a[v[i].y])
        {
            r[++rc]=i;
            k+=v[i].z;
            val=a[v[i].y];
            for(j=1;j<=n;j++) if(a[j]==val) a[j]=a[v[i].x];
        }
    }

    g<<k<<"\n"<<rc<<"\n";
    for(i=1;i<=rc;i++) g<<v[r[i]].y<<" "<<v[r[i]].x<<"\n";

    f.close();
    g.close();
    return 0;
}