#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,vaz[200007],ct,poz,tata[400007],muchie[200007][3];
long long s=0;
int search_tata(int nod)
{
    int x=nod;
    while(x!=tata[x]) x=tata[x];
    return x;
}
struct element
{
    int x,y,cost;
    bool operator<(const element&aux) const
    {
        if(cost<aux.cost) return true;
        else if(cost==aux.cost&&x<aux.x) return true;
        else if(cost==aux.cost&&x==aux.x&& y<aux.y) 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);
    //for(int i=1;i<=m;i++) printf("%d %d %d\n",v[i].x,v[i].y,v[i].cost);
    while(ct<(n-1))
    {
        poz++;
        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]=search_tata(v[poz].y);
            }
            else
            {
                vaz[v[poz].y]=1;
                tata[v[poz].y]=search_tata(v[poz].x);
            }
        }
        else if(search_tata(v[poz].x)!=search_tata(v[poz].y))
        {
            ct++;
            muchie[ct][1]=v[poz].x;
            muchie[ct][2]=v[poz].y;
            s+=v[poz].cost;
            tata[search_tata(v[poz].y)]=search_tata(v[poz].x);
        }

    }
    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]);

}