#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int viz[10000], dist[10000], mat[10000][10000], n, m, t[10000];
#define inf 99999999
int get_min_node(int n)
{
    int v, i;
    for (i=1; i<=n; i++)
    {
        if(!viz[i])
        {
            v = i;
            break;
        }
    }
    for(i=1; i<=n; i++)
        if(!viz[i] && (dist[i] < dist[v]))
            v = i;
    return v;
}
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 = get_min_node(n); // 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++;
                    }

    }
    int s = 0;
    for (int i = 1; i <= n; i++)
        s = s + mat[i][t[i]];
        g<<s<<endl;
        g<<n-1<<endl;
	for (int i = 2; i <= n; i++)
    g<< t[i]<<" "<< i<<" "<<endl; //cost muchie = 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);
}