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

struct tip
{

    long x,y,c;

} a[400010], b[400010];

long tata[200010],rang[200010],sol1[200010],sol2[200010];
long aux[20010];
long i,j,n,m,ct,k,v,w;

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

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

    return r;
}

long uneste (long x, long y)
{

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

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

}

bool cmp(tip a, tip b)
{
    if(a.c>b.c) return 0;
    else return 1;
}

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].c;
        aux[a[i].c]++;

    }

    sort(a+1,a+m+1,cmp);

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

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


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

        if(v!=w)
        {
            k++;
            ct+=b[i].c;
            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;
}