# include <cstdio>
# include <algorithm>
using namespace std;
struct edge{int x,y,w;} e[400001];
int n,m,i,k,mini,a[200001],b[800001];
bool cmp(edge i,edge j)
{
    return(i.w<j.w);
}
void read()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);

    }
}
void Kruskal()
{
    for(i=1;i<=m;i++)
    {
        //printf("%d %d %d %d\n",e[i].x,e[i].y,a[e[i].x],a[e[i].y]);
        if(a[e[i].x]!=a[e[i].y])
            {
             mini+=e[i].w;
             int x=min(a[e[i].x],a[e[i].y]);
             int xx=a[e[i].x],yy=a[e[i].y];
             for(int j=1;j<=n;j++)
                  if(a[j]==xx||a[j]==yy)
                      a[j]=x;
             b[++k]=e[i].x;
             b[++k]=e[i].y;
            }
         //printf("%d %d %d %d\n",e[i].x,e[i].y,a[e[i].x],a[e[i].y]);

    }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    sort(e+1,e+m+1,cmp);
    for(i=1;i<=n;i++)
         a[i]=i;
    Kruskal();
    printf("%d\n%d\n",mini,k/2);
    for(i=1;i<=k;i+=2)
        printf("%d %d\n",b[i],b[i+1]);
    return 0;
}