#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,vaz[200007],ct,poz,tata[200007],muchie[200007][3];
long long s=0;
int search_tata(int nod)
{
    int x=nod;
    while(x!=tata[x]) x=tata[x];
    while(nod!=x)
    {
        int aux=tata[nod];
        tata[nod]=x;
        nod=aux;
    }
    return x;
}
struct element
{
    int x,y,cost;
    bool operator<(const element&aux) const
    {
        if(cost<aux.cost) return true;
        else return false;
    }

}v[400007];
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d ",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
    sort(v+1,v+m+1);
    while(ct<(n-1))
    {
        poz++;
        int sx=search_tata(v[poz].x),sy=search_tata(v[poz].y);
        if(vaz[v[poz].x]==0&&vaz[v[poz].y]==0)
        {
            ct++;
            vaz[v[poz].x]=1;
            vaz[v[poz].y]=1;
            muchie[ct][1]=v[poz].x;
            muchie[ct][2]=v[poz].y;
            s+=v[poz].cost;
            tata[v[poz].x]=v[poz].x;
            tata[v[poz].y]=v[poz].x;
        }
        else if(vaz[v[poz].x]==0||vaz[v[poz].y]==0)
        {
            ct++;
            muchie[ct][1]=v[poz].x;
            muchie[ct][2]=v[poz].y;
            s+=v[poz].cost;
            if(vaz[v[poz].x]==0)
            {
                vaz[v[poz].x]=1;
                tata[v[poz].x]=sy;
            }
            else
            {
                vaz[v[poz].y]=1;
                tata[v[poz].y]=sx;
            }
        }
        else if(sx!=sy)
        {
            ct++;
            muchie[ct][1]=v[poz].x;
            muchie[ct][2]=v[poz].y;
            s+=v[poz].cost;
            tata[sy]=sx;
        }

    }
    printf("%lld\n",s);
    printf("%d\n",n-1);
    for(int i=1;i<n;i++)
        printf("%d %d\n",muchie[i][1],muchie[i][2]);

}