#include <fstream>
#include <algorithm>
#define MMAX 400002
#define NMAX 200002
using namespace std;
ifstream  fin("apm.in");
ofstream fout("apm.out");
int N,M,sef[NMAX],nr[NMAX],cnt,r;

struct triplet
{
    int x,y,c;
}v[MMAX];

struct solutia
{
    int x,y;
}sol[NMAX];

void citire()
{
   fin>>N>>M;

   for(int i=1; i<=M; i++)
   {
       fin>>v[i].x>>v[i].y>>v[i].c;
   }
}

int cmp(triplet a, triplet b)
{
    if(a.c<b.c)
    {
        return 1;
    }
    return 0;
}

int cauta_sef(int poz)
{
    int z,p=poz;

    while(sef[p]!=p)
    {
        p=sef[p];
    }
    z=p;

    p=poz;
    while(sef[p]!=p)
    {
        int d=sef[p];
        sef[p]=z;
        p=d;
    }

    return z;
}

void afisare()
{
    fout<< r << "\n";
    fout<< N-1 << "\n";
    for(int i=1; i<=N-1; i++)
    {
        fout<< sol[i].x << " " << sol[i].y << "\n";
    }
}

int main()
{
    citire();

    sort(v+1,v+1+M,cmp);

    for(int i=1; i<=N; i++)
    {
        sef[i]=i;
        nr[i]=1;
    }

    cnt=r=0;
    for(int i=1; i<=M; i++)
    {
        int x=sef[v[i].x];
        int y=sef[v[i].y];
        if(x!=y)
        {
            r+=v[i].c;
            cnt++;
            sol[cnt].x=v[i].x;
            sol[cnt].y=v[i].y;
            //fout<< v[i].x << " " << v[i].y << " " << r << "\n";

            if(nr[x]<nr[y])
            {
                sef[x]=y;
                nr[y]+=nr[x];
            }
            else
            {
                sef[y]=x;
                nr[x]+=nr[y];
            }
        }
    }

    afisare();

    /*for(int i=1; i<=M; i++)
    {
        fout<< v[i].x << " " << v[i].y << " " << v[i].c << "\n";
    }
    */

    return 0;
}