#include <fstream>
#include<algorithm>
#define MMAX 400001
#define NMAX 200001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {int x, y; int c;};

muchie G[MMAX], sol[MMAX];
int n, m, nr;
int c[NMAX], h[NMAX];
int costmin;

void citire();
void kruskal();
int Find(int x);
void Union(int i, int j);
muchie ExtrageMin(int &n);
void combinare(int rad, int n);
void afisare();

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    int i, rad;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>G[i].x>>G[i].y>>G[i].c;
    for(rad=m/2;rad>0;rad--) combinare(rad, m);
}

void kruskal()
{
    int c1, c2, i;
    muchie cost;
    for(i=1;i<=n-1;i++)
    {
        cost=ExtrageMin(m);
        c1=Find(cost.x);
        c2=Find(cost.y);
        if(c1!=c2)
        {
            costmin+=cost.c;
            //fout<<cost.x<<' '<<cost.y<<'\n';
            nr++; sol[nr].x=cost.x; sol[nr].y=cost.y;
            Union(c1, c2);
        }
        else i--;
    }
}

void combinare(int rad, int sn)
{
    int fiu, tata, x;
    muchie aux;
    x=G[rad].c; aux=G[rad];
    tata=rad; fiu=2*rad;
    while(fiu<=sn)
    {
        if(fiu+1<=sn&&G[fiu].c>G[fiu+1].c) fiu++;
        if(x>G[fiu].c)
        {
            G[tata]=G[fiu];
            tata=fiu; fiu=2*tata;
        }
        else break;
    }
    G[tata]=aux;
}

muchie ExtrageMin(int &n)
{
    muchie x=G[1];
    G[1]=G[n]; n--;
    combinare(1, n);
    return x;
}

int Find(int x)
{
    int aux, a;
    aux=x;
    while(c[aux]!=0) aux=c[aux];
    while(c[x]!=0)
    {
        a=x; x=c[x]; c[a]=aux;
    }
    return aux;
}

void Union(int i, int j)
{
    if(h[i]<h[j]) c[i]=j;
    else
        if(h[i]>h[j]) c[j]=i;
        else
        {
            c[i]=j; h[j]++;
        }
}

void afisare()
{
    int i;
    fout<<costmin<<'\n'<<nr<<'\n';
    for(i=1;i<=nr;i++) fout<<sol[i].x<<' '<<sol[i].y<<'\n';
    fout.close();
}