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

struct tip{

int x,y,t;

}a[400001], b[400001];

int tata[200001],rang[200001],sol1[200001],sol2[200001];
int aux[2001];
int i,j,n,m,ct,k,v,w;

int radacina (int a)
{
    int r=a;
    while(tata[r]!=r)
    {
        r=tata[r];
    }

    while(tata[a]!=a)
    {
        int aux=tata[a];
        tata[a]=r;
        a=aux;
    }

    return r;
}

int uneste (int x, int y)
{

    if(rang[x]>rang[y])
        tata[y]=x;
    else tata[x]=y;

    if(rang[x]=rang[y])  rang[y]++;

}


int main()
{
     fin>>n>>m;

    for(i=1; i<=n; i++) tata[i]=i, rang[i]=i;

    for(i=1; i<=m; i++)
    {
        fin>>a[i].x>>a[i].y>>a[i].t;
        aux[a[i].t]++;

    }

    for(i=-1000;i<=1000;i++)
        aux[i]=aux[i-1]+aux[i];

    for(i=1;i<=m;i++)
        {
             b[aux[a[i].t]]=a[i];
             aux[a[i].t]--;
        }


        i=1;
        while(k<n-1)
        {
            v=radacina(b[i].x);
            w=radacina(b[i].y);

            if(v!=w)
            {
                k++;
                ct+=b[i].t;
                sol1[k]=b[i].x;
                sol2[k]=b[i].y;
                uneste(v,w);

            }
            i++;
        }

    fout<<ct<<'\n'<<n-1<<'\n';

    for(i=1;i<=n-1;i++) fout<<sol2[i]<<" "<<sol1[i]<<'\n';

    return 0;
}