#include <fstream>
#define NM 200001
#define INF 1001
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int c[NM][NM], t[NM], d[NM], viz[NM];
int n,m,i,j,x,y,cost;
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        c[i][j]=c[j][i]=INF;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        c[x][y]=c[y][x]=cost;
    }
    for(i=2;i<=n;i++)
    {
        d[i]=c[1][i];
        t[i]=1;
    }
    int ct=0; viz[1]=1;
    int k,im;
    for(k=2;k<=n;k++)
    {
        int dm=INF;
        for(i=2;i<=n;i++)
            if(viz[i]==0&&d[i]<dm)
        {
            im=i; dm=d[i];
        }
        viz[im]=1;
        ct=ct+dm;
        for(i=2;i<=n;i++)
            if(viz[i]==0&&d[i]>c[im][i])
        {
            d[i]=c[im][i]; t[i]=im;
        }
    }
    fout<<ct<<'\n';
    /*
    for(i=1;i<=n;i++)
        fout<<t[i]<<' ';
    */
    fout<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<' '<<t[i]<<'\n';
    return 0;
}