#include <fstream>
#include <algorithm>
#define Nmax 200005

using namespace std;

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

struct muchie{
int x, y, c;
}a[Nmax], sol[Nmax];

int n, m, tt[Nmax], k, sm;

bool cmp(muchie a, muchie b)
{
   // if(a.c == b.c)
     //   return a.x<b.x;
    return a.c<b.c;
}

int uppd(int x)
{
    int r=x, y;
    while(tt[r]!=r) r=tt[r];
    while(tt[x]!=x)
     {
        y = tt[x];
        tt[x] = r;
        x = y;
     }
    return r;
}

int upd(int x)
{
    int r=x, y;
    while(tt[r]!=r) r=tt[r];
    while(tt[x]!=x)
    {
        y = tt[x];
        tt[x] = r;
        x = y;
    }
    return r;
}

int main()
{
    f >> n >> m;
    for ( int i = 1; i <= m; i ++ )
        f >> a[i].x >> a[i].y >> a[i].c;
    sort(a+1, a+m+1, cmp);
    for ( int i = 1; i <= n; i ++ )
     tt[i]=i;
    for ( int i = 1; i <= m; i ++ )
    {
        int x1=a[i].x, y1=a[i].y;
        int X=upd(x1), Y=upd(y1);
        if(X!=Y)
        {
            sm+=a[i].c;
            tt[X]=Y;
            sol[++k]={x1, y1, 0};
        }
    }
        g << sm << '\n' << k << '\n';
    for (int i = 1; i <= k; i++)
        g << sol[i].x << ' ' << sol[i].y << '\n';


}