#include <fstream>
#define NMAX 200005

using namespace std;

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

struct muchie{int x, y, c;}
G[400002], sol[NMAX];

int n, m;
int tata[NMAX], h[NMAX];
int costmin;


void citire();
void kruskal();
int Find(int x2);
void Union(int u, int v);
void creare_heap();
void comb_heap(int i, int n);
muchie extrage_min(int &n);

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

void citire()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
       fin>>G[i].x>>G[i].y>>G[i].c;
}

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

int Find(int x)
{
    int rad, aux;
    rad=x;
    while(tata[rad])
        rad=tata[rad];

    aux=x;
    while(tata[x])
    {
        aux=x;
        x=tata[x];
        tata[aux]=rad;
    }
    return rad;
}

void Union(int u, int v)
{
    if(h[u]>h[v])
        tata[v]=u;
    else
    {
        tata[u]=v;
        if(h[u]==h[v])
            h[v]++;
    }
}

void creare_heap()
{
    int i;
    for(i=m/2; i>=1; i--)
        comb_heap(i, m);
}

void comb_heap(int i, int n)
{
    int fiu, tata, x;
    muchie aux;

    tata=i;
    fiu=2*i;
    x=G[i].c;
    aux=G[i];
    while(fiu<=n)
    {
        if(fiu+1<=n)
            if(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 extrage_min(int &n)
{
    muchie x=G[1];
    G[1]=G[n];
    n--;
    comb_heap(1, n);
    return x;
}