#include <cstdio>
#include <algorithm>
using namespace std;

struct muchie
{   int x,y,c;};
int ct=0,n,m,rad[200000];
struct muchie u[400000];

bool cmp(struct muchie a,struct muchie b)
{   return(a.c<b.c);};

int getrad(int x)
{   if(rad[x]!=x)rad[x]=getrad(rad[x]);
    return rad[x];
}

void kruskal()
{   int i,x=1,a=u[1].x,b=u[1].y;
    for(i=1;i<=n;i++)rad[i]=i;
    for(i=1;i<n;i++)
    {while((x<m)&&(getrad(a)==getrad(b)))
        {x++;a=u[x].x;b=u[x].y;};
        if(a!=b){u[i]=u[x];ct+=u[i].c;rad[getrad(a)]=getrad(b);}}
}

int main()
{   int i,x,y,c;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)scanf("%d %d %d",&u[i].x,&u[i].y,&u[i].c);
    sort(u+1,u+m+1,cmp);
    kruskal();
    printf("%d\n%d\n",ct,n-1);
    for(i=1;i<n;i++)printf("%d %d\n",u[i].x,u[i].y);
}