#include <cstdio>
#include <algorithm>

using namespace std;

struct muchie
{
    int x,y,cost;
}u[400001],sol[200000];

int n,m,c[200001];
 int cst=0;

bool cmp(muchie u1,muchie u2)
{
    return (u1.cost<u2.cost);
}

void citire()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
       scanf("%d%d%d",&u[i].x,&u[i].y,&u[i].cost);
}


void kruskal()
{
    for(int i=1;i<=n;i++) c[i]=i;
    int i=0,k=0;
//printf("%d \n",n);
    while(k<n-1)
    {// printf("%d ",i);
        if(c[u[i].x]!=c[u[i].y])
            {
              sol[k]=u[i];
              cst+=u[i].cost;
              k++;
              for(int j=1;j<=n;j++)
                if(c[j]==c[u[i].x])
                   c[j]=c[u[i].y];
            }
         i++;
    }
}

void afisare()
{
    printf("%d\n%d\n",cst,n-1);
    for(int i=0;i<n-1;i++)
       printf("%d %d\n",sol[i].x,sol[i].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(u,u+m,cmp);

    kruskal();
    afisare();
    return 0;
}