#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

#define INF 9999999

// number of vertices in grapj


// create a 2d array of size 5x5
//for adjacency matrix to represent graph
struct prim
{
    int a,b;
} t[105];

int xx,yy,m,n,cost,G[105][105],sum,p,selected[105],no_edge;

int main ()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>xx>>yy>>cost;
        G[xx][yy]=G[yy][xx]=cost;


    }

    for(int i=1; i<=n; i++)
        selected[i]=-1;


    no_edge = 0;


    selected[1] = 1;

    int x;
    int y;


    while (no_edge < n- 1)
    {

        int minn = INF;
        x = 0;
        y = 0;

        for (int i = 1; i <= n; i++)
        {
            if (selected[i]==1)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (selected[j]==-1 && G[i][j])
                    {
                        if (minn > G[i][j])
                        {
                            minn = G[i][j];
                            x = i;
                            y = j;
                        }

                    }
                }
            }
        }
        t[++p].a=x;

        t[p].b=y;
        sum+=G[x][y];
        selected[y] = 1;
        no_edge++;
    }
    g<<sum<<endl;
    g<<p<<endl;
    for(int i=1; i<=p; i++)
        g<<t[i].a<<" "<<t[i].b<<endl;


    return 0;
}