#include <stdio.h>
#include <algorithm>
#define NMax 200002
#define Mmax 400002
using namespace std;
struct edge
{
   int x,y,c;
};
int n,m;
int cost=0;
int k=0;
edge a[Mmax];
int t[NMax],r[NMax],ind[NMax];
int sol[Mmax];
void citire()
{
    int i;
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a[i].x, &a[i].y, &a[i].c );
        ind[i]=i;
    }
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        r[i]=0;
    }
}
int Find(int x)
{
    if(t[x]!=x)
    {
        t[x]=Find(t[x]);
    }
    return t[x];
}
void Unite(int x, int y)
{
    if(r[x]>r[y])
    {
        t[y]=x;
    }
    else if(r[x]<r[y])
    {
        t[x]=y;
    }
    else
    {
        t[x]=y;
        r[y]++;
    }
}
bool comp(int x,int y)
{
    if(a[x].c < a[y].c)
        return 1;
    return 0;
}
void apm()
{
    sort(ind + 1, ind + m + 1, comp);
    for (int i= 1; i <= m; ++i)
        {
            if(Find(a[ind[i]].x)!=Find(a[ind[i]].y))
            {
                cost+=a[ind[i]].c;
                Unite(Find(a[ind[i]].x),Find(a[ind[i]].y));
                sol[k++]=ind[i];
            }
        }
    }


void write()
{
    freopen("apm.out", "w", stdout);

    printf("%d\n%d\n", cost, n - 1);
    for (int i = 0; i < k; ++i)
        printf("%d %d\n", a[ sol[i] ].x, a[ sol[i] ].y);
}

int main()
{
    citire();
    apm();
    write();

}