#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int a,b,cost;
};

int *p,*h;

int MakeSet(int u)
{
    p[u]=0;
    h[u]=0;
}

int FindSet(int u)
{
    if (p[u]==0)
        return u;
    p[u]=FindSet(p[u]);
    return p[u];
}

int Union(int u,int k)
{
    u=FindSet(u);
    k=FindSet(k);
    if (h[u]>h[k])
    {
        p[k]=u;
    }
    else
    {
        p[u]=k;
    }
    if(h[u]==h[k])
    {
        h[k]=h[k]+1;
    }
}

bool comparare(muchie x,muchie y)
{
    return x.cost<y.cost;
}



int main()
{int n,m,cost_total=0,nr=0,ok=1;
muchie *v,*v_minim;

    f>>n>>m;
    v=new muchie[m];
    v_minim=new muchie[m];
    p=new int[n+1];
    h=new int[n+1];
    for(int i=1;i<=n;i++)
    {
        p[i]=0;
        h[i]=0;
    }
    for(int i=0;i<m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].cost;
    }
    sort(v,v+m,comparare);
    for(int i=0;i<m && ok;i++)
    {
        if(FindSet(v[i].a)!=FindSet(v[i].b))
        {
            v_minim[nr]=v[i];
            nr++;
            Union(v[i].a,v[i].b);
            cost_total+=v[i].cost;
            if(nr>=n-1)
            {
                ok=0;
            }
        }
    }

    g<<cost_total<<"\n"<<nr<<"\n";
    for(int i=0;i<nr;i++)
    {
        g<<v_minim[i].a<<" "<<v_minim[i].b<<"\n";
    }

    return 0;
}