#include <fstream>
#define NMAX 20004
#define pinf 1000000

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int C[NMAX][NMAX],cmin[NMAX],prec[NMAX],M[NMAX],n,m,start=1;

void read();
void solve();
void write();

int main()
{
    read();
    solve();
    write();
    cin.close();cout.close();
    return 0;
}

void read()
{
    int i,x,y,c,j;
    cin>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            C[i][j]=pinf;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        C[x][y]=C[y][x]=c;
    }
}

void solve()
{
    int i,j,x=start,mn,aux;
    M[start]=1;
    for (i=1;i<=n;i++)
    {
        cmin[i]=C[start][i];
        prec[i]=start;
    }
    prec[start]=0;
    cmin[start]=0;
    for (i=1;i<n;i++)
    {
        mn=pinf;aux=x;x=0;
        for (j=1;j<=n;j++)
            if (cmin[j]<mn && M[j]==0)
        {
            mn=cmin[j];
            x=j;
        }
        prec[x]=aux;
        M[x]=1;
        for (j=1;j<=n;j++)
            if (cmin[j]>C[x][j] && M[j]==0)
        {
            cmin[j]=C[x][j];
            prec[j]=x;
        }
    }
}

void write()
{
    int i,cost=0;
    for (i=1;i<=n;i++)
        cost+=cmin[i];
    cout<<cost<<'\n'<<n-1<<'\n';
    for (i=1;i<=n;i++)
        if (i!=start)
        cout<<i<<' '<<prec[i]<<'\n';
}