#include <fstream>
#define INF 999999
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int d[21],t[21],sel[21],cost[10000][10000];
int n,m,s;
void prim(int nod)
{
    int i,j,min;
        for (i=1;i<=n;i++) d[i]=INF;
        d[nod]=0;t[nod]=0;
        for (i=1;i<=n;i++) {
            min=INF;
            for (j=1;j<=n;j++)
                if (d[j]<min && sel[j]==0)
                    {
                        min=d[j];
                        nod=j;
                    }
            sel[nod]=1;
            for (j=1;j<=n;j++)
                if (cost[nod][j]<d[j]&& nod!=j && cost[nod][j]!=0&&sel[j]==0)
                {
                    d[j]=cost[nod][j];
                    t[j]=nod;
                }

        }
}
int main()
{
    int i,j,x,y,c;
    f>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i==j) cost[i][j]=0;else
            cost[i][j]=INF;
    for (i=1;i<=m;i++) {
        f>>x>>y>>c;
        cost[x][y]=c;
        cost[y][x]=c;
    }
    prim(1);
    for (i=1;i<=n;i++)
        s+=d[i];
    g<<s<<'\n'<<n-1<<'\n';
     for (i=2;i<=n;i++)
        g<<i<<' '<<t[i]<<'\n';
    return 0;
}