#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int viz[100], dist[100], mat[100][100], n, m, t[100];
#define inf 99999999
int minKey(int key[], int mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 1; v <= n; v++)
    if (mstSet[v] == false && key[v] < min)
        min = key[v], min_index = v;

return min_index;
}
void prim(int n)
{
    int i, u, v;
    int nr = 0;

    for (u=1; u<=n; u++)
    {
        dist[u] = inf;
        viz [u] = 0;
    }
    dist[1] = 0;
	t[1] = -1;

    for(i=1; i<n; i++) // i<n
    {
        u = minKey(dist, viz); // nodul minim
        viz[u] = 1;

        if(dist[u] == inf)
            return;
        nr++;
       // g<<u<<" ";

        for(v=1; v<=n; v++)
            if(mat[u][v] && !viz[v] && mat[u][v] < dist[v])
                    {
                        t[v] = u, dist[v] = mat[u][v];
                        nr++;
                    }

    }
    g<<n<<endl;
    int s = 0;
    for (int i = 1; i <= n; i++)
        s = s + mat[i][t[i]];
        g<<s<<endl;
	for (int i = 2; i <= n; i++)
    g<< t[i]<<" "<< i<<" " << mat[i][t[i]]<<endl;
}
int main ()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        f>>x>>y>>c;
        mat[x][y] = mat[y][x] = c;
    }
    prim(n);
}