#include <fstream>
#define inf 100000000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,start=1;
int cmin[1001],uz[1001],tata[1001],v[1001];
struct lista
{
    int x,co;
}G[1001][1001];

void citire();
void prim();

int main()
{
    citire();
    prim();
}

void citire()
{
    int i,l,c,cost;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>l>>c>>cost;
        G[l][++v[l]].x=c;
        G[c][++v[c]].x=l;
        G[l][v[l]].co=cost;
        G[c][v[c]].co=cost;
    }
    uz[0]=1;
    uz[start]=1;
    for(i=1;i<=v[start];i++)
        cmin[G[start][i].x]=G[start][i].co;
    for(i=1;i<=n;i++)
    {
        if(cmin[i]==0)
            cmin[i]=inf;
        tata[i]=start;
    }
    tata[start]=0;
    cmin[start]=0;
}

void prim()
{
    int i,costmin,j,k,minimvf,tatavf,suma=0;
    for(i=1;i<=n-1;i++)
    {
        while(uz[0]<n)
        {
            costmin=inf;
            for(j=1;j<=n;j++)
                if(uz[j])
                {
                    for(k=1;k<=v[j];k++)
                        if(G[j][k].co<costmin && uz[G[j][k].x]==0)
                        {
                            costmin=G[j][k].co;
                            minimvf=G[j][k].x;
                            tatavf=j;
                        }
                }
            tata[minimvf]=tatavf;
            cmin[minimvf]=costmin;
            uz[minimvf]=1;
            uz[0]++;
        }

    }
    for(i=1;i<=n;i++)
        suma+=cmin[i];
    fout<<suma<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<' '<<tata[i]<<'\n';
}