#include <fstream>
#define NMAX 200002
#define MAX 400002

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");


struct muchie
{
    int x, y, cost;
    friend bool operator < (muchie a, muchie b);
    friend bool operator > (muchie a, muchie b);
    friend bool operator >= (muchie a, muchie b);
    friend bool operator <= (muchie a, muchie b);
};

bool operator < (muchie a, muchie b)
{return a.cost < b.cost;}
bool operator > (muchie a, muchie b)
{return a.cost > b.cost;}
bool operator >= (muchie a, muchie b)
{return a.cost >= b.cost;}
bool operator <= (muchie a, muchie b)
{return a.cost <= b.cost;}

int n, m;
int cx, cy, nrsel, sum;
muchie H[NMAX];
muchie A[NMAX];
int tata[MAX], h[MAX]; /// h[i] h arbore cu rad i;

int Find(int x); ///cauta radacina x
void Union(int x, int y); ///reuneste arborii x si y

void creare();
void combinare(int n, muchie H[], int poz);
muchie extrageMin(int &n, muchie H[]);

int main()
{muchie mmin;
int i;

    creare();
    while(nrsel < n - 1)
    {
        mmin = extrageMin(m, H);
        cx = Find(mmin.x);
        cy = Find(mmin.y);
        if(cx != cy)
        {
            nrsel++;
            A[nrsel] = mmin;
            sum += mmin.cost;
            Union(cx, cy);

        }
    }

    fout << sum << '\n';
    fout << n - 1 << '\n';
    for(i=1;i<n;i++)
        fout << A[i].x << A[i].y << A[i].cost << '\n';

    fout.close();

  return 0;
}

int Find(int x) ///cauta radacina x /// O(n)
{int rad, aux;

    while(tata[rad]) rad = tata[rad];
    //compresia drum
    while(tata[x])
    {
        aux = tata[x];
        tata[x] = rad;
        x = aux;
    }
    return rad;
}

void Union(int x, int y) ///reuneste arborii x si y
{
    if(h[x] < h[y])
        tata[x] = y;
    else if(h[x] > h[y])
        tata[y] = x;
    else {tata[y] = x; h[x]++;}
    ///O(1)

}

void combinare(int n, muchie H[], int poz)
{muchie x=H[poz];
int fiu, tata;

 tata=poz;
 fiu=2*tata;
 while (fiu<=n)
       {
         if (fiu+1<=n && H[fiu+1]<H[fiu]) fiu++;
         if (x <= H[fiu]) break;
         H[tata]=H[fiu];
         tata=fiu;
         fiu=2*tata;
        }
  H[tata]=x;
}

void creare()
{int i;
 fin>>n>>m;

 for (i=1; i<=m; i++) fin >> H[i].x >> H[i].y >> H[i].cost;
 for (i=m/2; i>0; i--)
     combinare(m, H, i);
}

muchie extrageMin(int &n, muchie H[])
{muchie minim=H[1];
 H[1]=H[n--];
 combinare(n,H,1);
 return minim;
}